Divide Intervals Into Minimum Number Of Groups
01 · Problem
You are given a list of intervals, where intervals[i] = [left, right] covers every integer from left to right inclusive.
Split all the intervals into groups so that every interval belongs to exactly one group and no two intervals in the same group intersect. Two intervals intersect if they share at least one integer, so [1, 5] and [5, 8] intersect.
Return the minimum number of groups needed.
02 · Examples
intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
3
At point 5 the intervals [5,10], [1,5] and [1,10] all overlap, so at least 3 groups are required, and 3 suffice: {[1,5],[6,8]}, {[2,3],[5,10]}, {[1,10]}.
intervals = [[1,3],[5,6],[8,10],[11,13]]
1
No two intervals overlap, so they all fit in one group.
intervals = [[1,4],[4,6],[7,9]]
2
[1,4] and [4,6] share the point 4, so they need separate groups; [7,9] can join either. The answer is 2.
03 · Constraints
- 011 <= intervals.length <= 105
- 02intervals[i].length == 2
- 031 <= left <= right <= 106
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.