#2406

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Divide Intervals Into Minimum Number of Groups

Determine the minimum number of non-overlapping groups for a set of intervals using precise two-pointer scanning logic.

array two pointers greedy sorting heap priority queue

Problem Statement

You are given a list of intervals where each interval is represented as [start, end]. Your task is to divide these intervals into groups so that no two intervals in the same group overlap. Each interval must belong to exactly one group, and the goal is to minimize the total number of groups created.

Return the minimum number of groups required. Intervals can overlap in arbitrary ways, and efficient handling of edge overlaps is critical. For example, intervals like [[5,10],[6,8],[1,5],[2,3],[1,10]] require careful ordering and scanning to determine that at least three groups are needed.

Examples

Example 1

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]

Output: 3

We can divide the intervals into the following groups:

Group 1: [1, 5], [6, 8].
Group 2: [2, 3], [5, 10].
Group 3: [1, 10]. It can be proven that it is not possible to divide the intervals into fewer than 3 groups.

Example 2

Input: intervals = [[1,3],[5,6],[8,10],[11,13]]

Output: 1

None of the intervals overlap, so we can put all of them in one group.

Constraints

1 <= intervals.length <= 105
intervals[i].length == 2
1 <= lefti <= righti <= 106

Solution Approach

Sort Intervals and Initialize Data Structures

Sort intervals by their start values to process them in chronological order. Use a min-heap to track the end points of current active groups. This ensures that you can always assign a new interval to the earliest ending non-overlapping group.

Scan Intervals Using Two Pointers

Iterate through the sorted intervals with a two-pointer approach. For each interval, compare its start with the minimum end in the heap. If it does not overlap, extend that group; otherwise, create a new group. This invariant tracking guarantees you always maintain the minimum group count.

Finalize Minimum Group Count

After processing all intervals, the size of the heap represents the minimum number of groups needed. This method avoids unnecessary backtracking and handles cases with dense overlaps efficiently by always merging into the earliest compatible group.

Complexity Analysis

Metric	Value
Time	O(N + K)
Space	O(K)

Sorting takes O(N log N), scanning with a heap is O(N log K) in the worst case, where K is the number of concurrent groups. Overall, the approach efficiently handles up to 10^5 intervals with O(K) extra space for heap storage.

What Interviewers Usually Probe

They may hint at using sorting or heap to track overlapping ends.
Expect discussion about greedy assignment of intervals to earliest available groups.
They could ask about handling extreme overlaps or edge intervals in large datasets.

Common Pitfalls or Variants

Common pitfalls

Failing to sort intervals correctly can lead to assigning intervals to the wrong group.
Overlooking intervals that start exactly when another ends can inflate group count unnecessarily.
Using nested loops instead of a heap or counter may exceed time limits for large N.

Follow-up variants

Compute maximum number of overlapping intervals at any time, which directly informs group count.
Return the actual grouping of intervals rather than just the count, using similar scanning logic.
Handle intervals with additional constraints like weighted priorities or fixed group sizes.

FAQ

What is the optimal approach for Divide Intervals Into Minimum Number of Groups?

Use two-pointer scanning with a min-heap to track end points and greedily assign each interval to the earliest non-overlapping group.

Can overlapping intervals start or end at the same point?

Yes, intervals with identical start or end points require careful handling to maintain minimal group count without overlaps.

Does the algorithm require sorting the intervals first?

Yes, sorting by start values is essential to ensure the greedy two-pointer invariant correctly assigns intervals to groups.

What is the time complexity of this solution?

Sorting takes O(N log N) and heap operations take O(N log K), where K is the number of concurrent groups, making it efficient for large inputs.

How does GhostInterview handle edge overlaps?

It visually tracks interval assignments and heap updates to ensure intervals starting at the end of another are assigned without creating extra groups.

terminal

Solution

Solution 1: Greedy + Priority Queue (Min Heap)

First, we sort the intervals by their left endpoints. We use a min heap to maintain the rightmost endpoint of each group (the top of the heap is the minimum of the rightmost endpoints of all groups).

1

2

3

4

5

6

7

8

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        q = []
        for left, right in sorted(intervals):
            if q and q[0] < left:
                heappop(q)
            heappush(q, right)
        return len(q)

Continue Practicing

#2234 maximum total beauty of the gardens #2503 maximum number of points from grid queries #2271 maximum white tiles covered by a carpet