Interview Slot Calendar
An interview-scheduling tool receives a list of busy intervals from a panel of interviewers. To suggest meeting times, the tool needs the merged set of busy intervals (no overlaps, sorted by start) so the UI can render the free slots in between.
Problem
Given a list of closed intervals [start_i, end_i] with start_i ≤ end_i, return the merged list of intervals where any overlapping or touching intervals have been collapsed into one. Two intervals [a, b] and [c, d] should be merged if c ≤ b.
Input
An integer n (1 ≤ n ≤ 10^5) and a list of n intervals. Each interval has integer endpoints in [0, 10^9].
Output
A list of merged intervals, sorted by start ascending, with no overlaps or touches.
Constraints
- 1 ≤ n ≤ 100,000
- 0 ≤ start ≤ end ≤ 10^9
- Intervals may be given in any order
- Touching intervals (b == c) merge into [a, d]
Examples
Example 1
Input
[[1, 3], [2, 6], [8, 10], [9, 12]]
Output
[[1, 6], [8, 12]]
[1,3] and [2,6] overlap → [1,6]. [8,10] and [9,12] overlap → [8,12].
Example 2
Input
[[3, 5], [5, 7]]
Output
[[3, 7]]
Touching at 5 — merge per spec.