Find Maximal Uncovered Ranges

Find Maximal Uncovered Ranges

What is this problem about?

The Find Maximal Uncovered Ranges interview question gives you a total range $[0, n]$ and a list of sub-intervals that are "covered." You need to find all parts of the range $[0, n]$ that are not covered by any of the given intervals. The output should be a list of these missing intervals, sorted by their start points.

Why is this asked in interviews?

Meta use this to test proficiency with Interval and Sorting interview patterns. It’s a practical problem related to memory management (finding free blocks), scheduling (finding empty time slots), and graphics. It evaluation your ability to handle overlapping intervals and correctly identify the gaps between them.

Algorithmic pattern used

This is an Interval Merging and Complement problem.

1. Sort the given covered intervals by their start points.
2. Merge any overlapping or adjacent intervals so you have a list of disjoint covered ranges.
3. Iterate through the disjoint ranges. The "gaps" between the end of one range and the start of the next are the uncovered ranges.
4. Don't forget to check the gap between 0 and the first interval, and the gap between the last interval and $n$.

Example explanation

Total range [0, 10]. Covered: [[1, 2], [5, 8], [2, 3]]

1. Sort: [[1, 2], [2, 3], [5, 8]].
2. Merge: [[1, 3], [5, 8]].
3. Find Uncovered:
   • Gap before [1, 3]: [0, 0]. (If the range starts at 1).
   • Gap between [1, 3] and [5, 8]: [4, 4].
   • Gap after [5, 8]: [9, 10]. Result: [[0, 0], [4, 4], [9, 10]].

Common mistakes candidates make

• Not Sorting: Failing to sort the intervals, which makes merging impossible in linear time.
• Boundary conditions: Missing the gaps at the very beginning (0) or the very end ($n$).
• Off-by-one: Incorrectly calculating the start/end of the gaps (e.g., returning [3, 5] instead of [4, 4]).

Interview preparation tip

Always handle interval problems by sorting by start time first. It turns a chaotic set of ranges into an ordered sequence where you only need to compare the "current end" with the "next start."