Problem Description

You are given a 2D integer array intervals where intervals[i] = [left_i, right_i] represents an inclusive interval [left_i, right_i].

Your task is to divide these intervals into groups with the following requirements:

• Each interval must be placed in exactly one group
• No two intervals in the same group can intersect with each other

You need to find the minimum number of groups required to accommodate all intervals.

Two intervals are considered to intersect if they share at least one common number. For example:

• [1, 5] and [5, 8] intersect because they both contain the number 5
• [1, 3] and [4, 6] do not intersect because they have no common numbers

The solution uses a greedy approach with a min heap. After sorting intervals by their left endpoints, it maintains a heap of the rightmost endpoints of each group. For each interval, if its left endpoint is greater than the minimum right endpoint in the heap (meaning it doesn't overlap with that group), it can reuse that group by replacing the old right endpoint with the current interval's right endpoint. Otherwise, a new group is needed. The final number of groups is the size of the heap.

Intuition

Think of this problem like scheduling meetings in conference rooms. Each interval is a meeting that needs a room, and overlapping meetings cannot share the same room.

The key insight is that at any point in time, the number of groups we need equals the maximum number of intervals that overlap at that moment. This is similar to asking: "What's the maximum number of meetings happening simultaneously?"

To efficiently track this, we can process intervals in order of their start times. When we encounter a new interval, we need to decide: can it reuse an existing group (room), or do we need a new one?

Here's the critical observation: if we have multiple groups available, which one should we assign the current interval to? We should choose the group that ends earliest (has the smallest right endpoint). Why? Because this greedy choice maximizes our chances of reusing groups for future intervals.

This naturally leads us to use a min heap to track the right endpoints of all active groups. The heap always gives us quick access to the group that ends earliest:

• If the current interval's left endpoint > heap's minimum (earliest ending group), the current interval can reuse that group since they don't overlap
• Otherwise, all existing groups overlap with the current interval, so we need a new group

By maintaining this heap and processing intervals in sorted order, we ensure we're always making the optimal decision about group assignment. The final heap size represents the minimum number of groups needed, as it contains the right endpoint of each group that couldn't be merged with any other.

Learn more about Greedy, Two Pointers, Prefix Sum, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a greedy strategy combined with a min heap data structure:

Step 1: Sort the intervals

sorted(intervals)

We sort all intervals by their left endpoints. This ensures we process intervals in chronological order of their start times, which is crucial for making optimal grouping decisions.

Step 2: Initialize a min heap

q = []

We use a min heap q to track the right endpoints of each group. The heap maintains the invariant that the smallest right endpoint (the group that ends earliest) is always at the top.

Step 3: Process each interval For each interval [left, right] in sorted order:

if q and q[0] < left:
    heappop(q)

• Check if the heap is not empty and if the minimum right endpoint in the heap (top element q[0]) is less than the current interval's left endpoint
• If true, it means the current interval doesn't overlap with the group that ends earliest
• We can reuse this group by removing its old right endpoint with heappop(q)

heappush(q, right)

• Push the current interval's right endpoint into the heap
• This either represents updating an existing group (if we popped earlier) or creating a new group

Step 4: Return the result

return len(q)

The size of the heap at the end represents the minimum number of groups needed. Each element in the heap corresponds to one group's right endpoint.

Time Complexity: O(n log n) where n is the number of intervals - sorting takes O(n log n) and each heap operation takes O(log n) for n intervals.

Space Complexity: O(n) for the heap which can contain at most n elements in the worst case when all intervals overlap.

Example Walkthrough

Let's walk through the algorithm with intervals: [[0,3], [5,8], [1,5], [6,10], [2,7]]

Step 1: Sort intervals by left endpoint After sorting: [[0,3], [1,5], [2,7], [5,8], [6,10]]

Step 2: Process each interval with the min heap

Visual Timeline:

Group 1: [0,3]--------[5,8]
Group 2:   [1,5]----------[6,10]
Group 3:     [2,7]
         0 1 2 3 4 5 6 7 8 9 10

Result: The heap has 3 elements, so we need 3 groups minimum.

The key insight: When we process [5,8], the heap's minimum is 3 (Group 1's endpoint). Since 3 < 5, interval [5,8] doesn't overlap with Group 1, so we can assign it there. Similarly, [6,10] can reuse Group 2. The heap always tells us which group ends earliest and is therefore the best candidate for reuse.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by two operations:

1. Sorting the intervals: sorted(intervals) takes O(n × log n) time where n is the number of intervals
2. The for loop runs n times, and in each iteration:
   • heappop(q) operation (when condition is met): O(log k) where k is the size of heap
   • heappush(q, right) operation: O(log k) where k is the size of heap

Since the heap size is at most n, each heap operation is O(log n). The total time for all heap operations is O(n × log n).

Therefore, the overall time complexity is O(n × log n) + O(n × log n) = O(n × log n).

Space Complexity: O(n)

The space complexity comes from:

1. The heap q which can contain at most n elements in the worst case (when all intervals overlap)
2. The sorted function creates a new sorted list which takes O(n) space

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overlap Condition

A critical pitfall is misunderstanding when intervals overlap. The problem states that intervals intersect if they share at least one common number, meaning [1, 5] and [5, 8] DO overlap because they both contain 5.

Incorrect Implementation:

# Wrong: This treats touching intervals as non-overlapping
if min_heap and min_heap[0] < start:  # Should be <= 
    heapq.heappop(min_heap)

Correct Implementation:

# Intervals can only be in the same group if they don't share ANY number
# So we can reuse a group only when: end_of_group < start_of_new_interval
if min_heap and min_heap[0] < start:
    heapq.heappop(min_heap)

2. Using Maximum Heap Instead of Minimum Heap

Some might think we need to track the latest ending intervals, but we actually need the earliest ending ones to make optimal reuse decisions.

Why min heap is correct:

• We want to find groups that have already ended to reuse them
• The group with the smallest right endpoint is most likely to have ended before a new interval starts
• This greedy choice minimizes the total number of groups

3. Forgetting to Sort the Intervals

Processing intervals in random order breaks the algorithm's logic.

Without sorting:

# Wrong: Processing in arbitrary order
for start, end in intervals:  # Missing sort!
    # Logic fails because we might process [10, 15] before [1, 5]

With proper sorting:

for start, end in sorted(intervals):
    # Now we process intervals in chronological order of start times

4. Off-by-One Error in Overlap Check

Remember that intervals are inclusive on both ends. The condition heap[0] < start is correct because:

• If heap[0] = 5 (group ends at 5) and start = 6 (new interval starts at 6), they don't overlap
• If heap[0] = 5 and start = 5, they DO overlap (both contain 5)

Test your understanding:

• [1, 3] and [4, 6]: Don't overlap (3 < 4) ✓
• [1, 3] and [3, 6]: Do overlap (share 3) ✓
• [1, 5] and [6, 10]: Don't overlap (5 < 6) ✓