Overview
MediumSort, then sweep · overlap ⇔ b.start ≤ a.end
Intervals are start–end ranges; sorting them by start makes overlaps easy to spot.
The idea
Almost every interval problem starts by sorting on start (or end). Two intervals overlap exactly when the later one begins no after the earlier one ends.
A1–4
B3–6
Step 1 of 3. Two events on a timeline (0–7). Event A runs 1–4, Event B runs 3–6. Do they clash? A 1–4, B 3–6.
1/3
Optimal
timeO(n log n)spaceO(n)
Order unlocks a linear scan.
1intervals.sort((a, b) => a[0] - b[0]);2const overlap = (a, b) => b[0] <= a[1];Input
- grid
- 2 × 8
Memory
- cells marked
- 8
- A
- 1–4
- B
- 3–6
Output
- overlap
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- [[1,3], [2,6], [8,10]]
- Output:
- [[1,6], [8,10]]
- Explanation:
- Sorted by start, [2,6] begins before [1,3] ends, so they merge to [1,6]. 8 > 6, so a new interval starts.
Example 2
- Input:
- [[1,3], [4,6]]
- Output:
- no merge
- Explanation:
- Touching is not overlapping unless the problem says it is — 4 > 3. Read that boundary carefully; it is where these problems are won or lost.
Finished the walkthrough? Add it to your streak.