Pseudo-code:

text
sort(intervals)
groups = []
for interval in intervals:
    placed = false
    for group in groups:
        last_interval = group.last()
        if interval.start > last_interval.end:
            group.add(interval)
            placed = true
            break
    if not placed:
        groups.add([interval])
return groups.length

Complexity Analysis: The time complexity is $O(N^2)$ in the worst case. If all intervals overlap (e.g., [1, 10], [2, 10], [3, 10]), we create a new group for every interval. For the $i$-th interval, we might iterate through $i-1$ groups before creating a new one. With constraints allowing up to $10^5$ intervals, an $O(N^2)$ solution requires roughly $10^{10}$ operations, resulting in a Time Limit Exceeded (TLE) error.

Core Insight for Divide Intervals Into Minimum Number of Groups

The transition from the brute force approach to the optimal solution relies on optimizing how we search for an available group.

In the brute force method, we iterate through all groups to find one that ends before the current interval starts. However, we don't need to check every group. We only care about the group that finishes earliest.

If the current interval starts after the earliest-ending group finishes, we can reuse that group. If the current interval starts before even the earliest-ending group finishes, it is impossible to reuse any existing group (because all other groups end even later). In this case, we are forced to create a new group.

Therefore, we only need to track the end times of the active groups. Specifically, we need efficient access to the minimum end time. A Min-Heap (Priority Queue) is the perfect data structure for this, allowing us to retrieve the minimum element in $O(1)$ and update it in $O(\log K)$.

Visual Description: Imagine plotting the intervals on a timeline. As we sweep from left to right (processing sorted intervals), the heap represents the "active wavefront" of intervals.

1. When we encounter a new interval, we look at the heap's top (the earliest end time).
2. If the new interval starts strictly after that end time, the conflict is resolved. We "remove" the old interval (pop from heap) and extend that group with the new interval (push new end time).
3. If it overlaps, we cannot resolve the conflict. We add the new interval's end time to the heap, effectively increasing the "height" or number of concurrent groups.

Execution Flow

Consider intervals = [[5,10], [6,8], [1,5], [2,3], [1,10]].

1. Sort: [[1,5], [1,10], [2,3], [5,10], [6,8]]

2. Initialize: min_heap = []

3. Process [1, 5]:

   • Heap is empty.
   • Push 5.
   • min_heap = [5] (Size: 1)

4. Process [1, 10]:

   • start = 1. min_heap.top() = 5.
   • Is 1 > 5? No. Overlap exists.
   • Push 10.
   • min_heap = [5, 10] (Size: 2)

5. Process [2, 3]:

   • start = 2. min_heap.top() = 5.
   • Is 2 > 5? No. Overlap exists.
   • Push 3.
   • min_heap = [3, 5, 10] (Size: 3) (Note: Heap reorders to maintain min property).

6. Process [5, 10]:

   • start = 5. min_heap.top() = 3.
   • Is 5 > 3? Yes. No overlap.
   • Pop 3 (Reuse the group that ended at 3).
   • Push 10.
   • min_heap = [5, 10, 10] (Size: 3)

7. Process [6, 8]:

   • start = 6. min_heap.top() = 5.
   • Is 6 > 5? Yes. No overlap.
   • Pop 5.
   • Push 8.
   • min_heap = [8, 10, 10] (Size: 3)

8. Result: Heap size is 3. Return 3.

Proof of Correctness

The correctness hinges on the property that min_heap.size() tracks the maximum number of overlapping intervals encountered so far.

By sorting by start time, we ensure that when we consider a new interval, all previously processed intervals started at or before the current time. When we check min_heap.top() < current.start, we are asking: "Is there any group that finished before this new task needs to start?"

If the answer is yes, we greedily take that slot. This is optimal because reusing a group that finished earlier leaves groups that finish later available for future intervals that might start later. If the answer is no (the earliest finishing group is still busy), then every active group is busy. We are mathematically forced to allocate a new group. Thus, the number of groups never exceeds the necessary minimum.

Reference Implementation

C++ Solution for LeetCode 2406

cpp
class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        // Sort intervals by start time
        sort(intervals.begin(), intervals.end());
        
        // Min-heap to store end times of the groups
        // priority_queue is max-heap by default, so we use 'greater' for min-heap
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for (const auto& interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            
            // If the group with the earliest end time finishes before 
            // the current interval starts, we can reuse that group.
            if (!pq.empty() && pq.top() < start) {
                pq.pop();
            }
            
            // Add the current interval's end time to the heap
            // (either extending an existing group or starting a new one)
            pq.push(end);
        }
        
        // The size of the heap represents the number of active groups required
        return pq.size();
    }
};

Java Solution for LeetCode 2406

java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minGroups(int[][] intervals) {
        // Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Min-heap to store end times of active groups
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            
            // If the earliest ending group finishes strictly before the current start,
            // we can reuse that group (remove the old end time).
            if (!pq.isEmpty() && pq.peek() < start) {
                pq.poll();
            }
            
            // Add the new end time to the heap
            pq.offer(end);
        }
        
        // The size of the heap is the minimum number of groups needed
        return pq.size();
    }
}

Python Solution for LeetCode 2406

python
import heapq

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        # Sort intervals by start time
        intervals.sort()
        
        # Min-heap to store end times
        min_heap = []
        
        for start, end in intervals:
            # If the heap is not empty and the earliest ending group
            # finishes before the current interval starts, reuse it.
            if min_heap and min_heap[0] < start:
                heapq.heappop(min_heap)
            
            # Push the current interval's end time
            heapq.heappush(min_heap, end)
            
        # The size of the heap corresponds to the number of groups
        return len(min_heap)