Why is the answer the most intervals covering one point?

If k intervals all contain the same point, each must be in a different group, so you need at least k groups. And k groups are always enough: hand intervals out in order of start, putting each into any group whose last interval has already ended. A group is only unavailable while its interval covers the current start, so you never need more than the deepest overlap.

What is the difference from Meeting Rooms II?

Only the comparison. Here intervals are inclusive, so [1,5] and [5,8] share the point 5 and must go in different groups: a start equal to the earliest end opens a new group (start <= end). In Meeting Rooms II a meeting ending at 5 frees its room for one starting at 5 (start < end).

Can I use a min-heap instead?

Yes. Sort intervals by start and keep a min-heap of each group's last end. If the smallest end is less than the new start, pop it (that group is reused); push the new interval's end. The heap's size at the end is the answer. Same O(n log n), slightly more code.

Is there a way without sorting?

With values up to 10^6, a difference array works: add 1 at left and subtract 1 at right + 1, then take the largest prefix sum. That is O(n + V), where V is the largest value.

Divide Intervals Into Minimum Number of Groups

Q: Can I use a min-heap instead?

Yes. Sort intervals by start and keep a min-heap of each group's last end. If the smallest end is less than the new start, pop it (that group is reused); push the new interval's end. The heap's size at the end is the answer. Same O(n log n), slightly more code.

Q: Is there a way without sorting?

With values up to 10^6, a difference array works: add 1 at left and subtract 1 at right + 1, then take the largest prefix sum. That is O(n + V), where V is the largest value.

Split inclusive intervals into the fewest groups so that no two intervals in a group intersect, by counting the most intervals that cover a single point.

MediumSolve on LeetCode

Problem Understanding

Divide Intervals Into Minimum Number of Groups (LeetCode 2406): given inclusive intervals [left, right], split them into the fewest groups so that no two intervals in the same group intersect. Intervals that share even one point intersect.

Examples: [[5,10],[6,8],[1,5],[2,3],[1,10]] → 3; [[1,3],[5,6],[8,10],[11,13]] → 1.

The Intuition: Count the Deepest Overlap

The number of groups needed is the largest number of intervals stacked on one point, and two sorted lists find it:

Sort starts and ends separately. Which end belongs to which interval does not matter, only the order of events.
Walk the starts. If a start is at or before the earliest end not yet used, every group is still busy: open a new one.
Otherwise some interval has finished: move endPtr past it and reuse its group.

It is Meeting Rooms II with <= instead of <, because these intervals include their ends. For the opposite question, how many intervals to remove so none overlap, see Non-overlapping Intervals.

Interactive Walkthrough

5 INTERVALS · ENDS INCLUDED

INPUT

schedule

[5,10]

[6,8]

[1,5]

[2,3]

[1,10]

starts · sorted

not sorted yet

ends · sorted

not sorted yet

endPtr

Groups

5 intervals: the fewest groups with no overlap inside a group

Sort the starts: 1, 1, 2, 5, 6

Free preview: the first 3 of 9 steps

Intervals

The rule marks the start being read; under the timeline, starts and ends are walked by i and endPtr. Try Touching ends to see the inclusive comparison open a group where Meeting Rooms II would reuse a room.

Dry Run Table

Input: [[5,10],[6,8],[1,5],[2,3],[1,10]]. Sorted starts: 1, 1, 2, 5, 6. Sorted ends: 3, 5, 8, 10, 10.

start	ends[endPtr]	Action	Groups
1	3	1 ≤ 3: new group	1
1	3	1 ≤ 3: new group	2
2	3	2 ≤ 3: new group	3
5	3	5 > 3: reuse, endPtr → 1	3
6	5	6 > 5: reuse, endPtr → 2	3

Answer: 3.

The Solution Template

Two sorted arrays and two pointers.

Divide Intervals Into Minimum Number of Groups Code

1var minGroups = function(intervals) {
2    const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
3    const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
4    let groups = 0, endPtr = 0;
5    for (const start of starts) {
6        if (start <= ends[endPtr]) {
7            groups++;
8        } else {
9            endPtr++;
10        }
11    }
12    return groups;
13};

Edge Cases & Common Mistakes

Using < instead of <=: treats [1,5] and [5,8] as disjoint and undercounts.
Point intervals: [3,3] is valid and still overlaps anything containing 3.
Sorting the intervals and comparing neighbours: two non-adjacent intervals can still overlap; count overlaps, do not chain pairs.
One interval: one group.
Nested intervals: [1,10] contains [2,3]; they overlap and need separate groups.

Summary

Sort starts and ends separately; for each start, open a group if it is at or before the earliest unused end, otherwise reuse that group. The count is the deepest overlap. O(n log n) time, O(n) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Meeting Rooms II

Minimum Interval to Include Each Query