Find gaps between intervals
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of integer intervals `intervals`, where each interval is represented as `[start, end]` (inclusive), and `start <= end`.
Two intervals may overlap or touch (e.g., `[1,3]` and `[4,6]` touch if you consider integers, because there is no missing integer between 3 and 4). Your task is to find **all gaps** (missing ranges) **between** the covered portions of the number line.
More precisely:
1. Consider the union of all intervals.
2. Let `minCovered` be the smallest integer covered by any interval, and `maxCovered` be the largest integer covered by any interval.
3. Return a list of **all maximal missing integer ranges** within `[minCovered, maxCovered]` that are **not covered** by the union.
Return the gaps as a list of disjoint intervals `[gapStart, gapEnd]` (inclusive), sorted by `gapStart`.
### Example
- Input: `[[1,3],[7,10],[2,4]]`
- Covered union is `[1,4] ∪ [7,10]`
- Gaps within `[1,10]` are `[[5,6]]`
- Output: `[[5,6]]`
### Notes / Edge cases
- If the union is already contiguous (no gaps), return `[]`.
- Overlapping intervals should not create gaps.
- Intervals may be unsorted.
### Constraints (reasonable interview assumptions)
- `1 <= len(intervals) <= 2e5`
- Interval endpoints fit in 32-bit signed integers.
Quick Answer: This question evaluates interval manipulation and range-coverage reasoning, testing skills in sorting, merging overlapping ranges, and handling boundary conditions within the Coding & Algorithms domain.