2406. Divide Intervals Into Minimum Number of Groups

2406

MediumIntervals and Sweep LineSweep line / min-heap of end timesMaximum concurrent overlap

Divide Intervals Into Minimum Number of Groups

Given a 2D array intervals where intervals[i] = [left_i, right_i] is an inclusive interval, divide all intervals into groups so that no two intervals in the same group intersect (share any common number). Return the minimum number of groups needed. Two intervals intersect if they overlap at even a single point, e.g. [1,5] and [5,8] intersect because they share 5.

Open official problem prompt ↗

In plain English

Find the fewest groups so that within each group the intervals are pairwise disjoint — equivalently, find the maximum number of intervals that are simultaneously active at any point.

Picture it like this

Think of meeting rooms: each interval is a meeting, and two meetings clashing at any instant need separate rooms. The number of rooms you must book is the greatest number of meetings running at the same moment.

Example

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Why: At point 5, the intervals [5,10], [1,5], and [1,10] all overlap, so at least 3 groups are required and 3 suffice.

Constraints

1 <= intervals.length <= 10^5intervals[i].length == 21 <= left_i <= right_i <= 10^6

Pattern lesson

See the pattern, then code

Maximum concurrent overlap

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Any point covered by k intervals forces those k intervals into k different groups, so the answer is at least the peak overlap. Sweeping starts as +1 and ends as -1 (or greedily reusing a group whose interval already ended) achieves exactly that peak.

New words, made simpleKnow these before the algorithm

Inclusive interval: [a,b] covers every integer from a to b including both endpoints, so [1,5] and [5,8] share the point 5.
Concurrent overlap: The count of intervals that cover one particular point at the same time.
Sweep line: Processing sorted start/end events left to right, adding on a start and removing on an end.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try every point / brute force overlap

Quadratic pairwise checking is too slow at 10^5 intervals, and scanning up to 10^6 coordinates naively is fragile.

For each interval count how many others intersect it, or scan every coordinate counting cover.

Time O(n^2) or O(max_coord)Space O(1) to O(max_coord)

Best choiceSweep line with a min-heap of end times

Directly computes the peak overlap in one sorted pass with heap operations; optimal and clean.

Sort by start; keep a heap of open group end times, reuse a group when its earliest end precedes the current start, otherwise open a new one.

Time O(n log n)Space O(n)

The rule we keep true

Invariant

The heap always holds exactly the end times of the groups that are still 'open' (their last interval has not yet ended before the current start), so its size equals the number of intervals overlapping the current start point.

Why this is correct

Reasoning

A point covered by k intervals is a lower bound: those k intervals mutually intersect, needing k groups. The heap approach never opens a new group when an existing one is free (its end < current start, since intervals are inclusive), so the heap size never exceeds the true peak overlap; and it must grow to that peak when k intervals all remain open. Thus the final size equals the maximum concurrent overlap, which is both necessary and achievable.

The algorithm in three movesSay these aloud before coding

1Sort intervals by start time

heap ends = [5, 10] after [1,5],[1,10]

2Keep a min-heap of the end times of the currently open groups

add [2,3] -> [3,5,10] (peak size 3)

3For each interval, if the earliest ending group finished before this start, pop it (reuse that group)

[5,10]: pop 3, push 10 -> size stays 3

4Push the current interval's end onto the heap

5The final heap size is the maximum simultaneous overlap = the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,5]0

[1,10]1

[2,3]2

[5,10]3

[6,8]4

1 · Read[[5,10],[6,8],[1,5],[2,3],[1,10]]

2 · AskOrder by start?

3 · Update state[[1,5],[1,10],[2,3],[5,10],[6,8]]

4 · ResultProcess left to right

Key takeaway

Intervals sorted by start; at points 2–3 three intervals overlap, fixing the answer at 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Sort by start
Sorting tuples sorts by start first, letting us process intervals in the order they begin.
2
Lines 6Heap of open ends
A min-heap keyed on end time exposes the group that frees up soonest at heap[0].
3
Lines 8-9Reuse a finished group
If the earliest end is strictly less than the current start, that group's interval has ended (inclusive endpoints, so strict <) and can be reused.
4
Lines 10Assign the current interval
Push this interval's end; whether we popped or not, exactly one slot now holds it.
5
Lines 11Answer is heap size
The heap only grows when no group is free, so its final size is the maximum concurrent overlap.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single interval returns 1
All intervals identical need one group each -> n groups
Intervals that merely touch at an endpoint, e.g. [1,5] and [5,8], intersect and cannot share a group
Completely disjoint intervals all fit in one group

Common beginner mistakes

Using heap[0] <= start instead of < : because endpoints are inclusive, [1,5] and [5,8] overlap, so the free condition must be strict <
Forgetting that touching intervals count as intersecting
Trying to physically build the groups instead of just counting the peak overlap
Sorting by end time instead of start, which breaks the reuse logic

Check your understanding

Why does the minimum number of groups equal the maximum number of intervals overlapping at a single point?

Divide Intervals Into Minimum Number of Groups

Divide Intervals Into Minimum Number of Groups

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line