Divide Intervals Into Minimum Number of Groups

LeetCode 2406: Divide Intervals Into Minimum Number of Groups Solution & Explanation

Problem Overview

TL;DR: Sort the intervals by start time and use a min-heap to track the end times of active groups; the size of the heap represents the minimum number of groups required.

The LeetCode 2406 problem, "Divide Intervals Into Minimum Number of Groups," asks us to organize a collection of time intervals into the fewest number of non-overlapping groups possible. We are given a set of intervals [start, end]. We must assign every interval to a group such that no two intervals within the same group intersect. Two intervals are considered intersecting if they share any common numbers (e.g., [1, 5] and [5, 8] intersect).

This is a classic scheduling problem often phrased as finding the minimum number of resources (like conference rooms or servers) needed to handle a set of tasks that occur over specific time ranges.

Brute Force Approach for Divide Intervals Into Minimum Number of Groups

A naive approach to solve Divide Intervals Into Minimum Number of Groups involves maintaining a list of groups, where each group stores the intervals assigned to it.

1. Sort the intervals by start time.
2. Initialize a list of groups (each group is a list of intervals).
3. For each interval in the input:
   • Iterate through the existing groups.
   • Check if the current interval can fit into a group without overlapping with the last interval added to that group.
   • If a valid group is found, add the interval there.
   • If no valid group is found, create a new group containing this interval.
4. Return the total count of groups.

Pseudo-code:

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.

Algorithm Strategy: Greedy Patterns

1. Sort: First, sort the intervals array based on their start times. This allows us to process the timeline linearly. If start times are equal, the secondary sort order (end times) does not strictly matter for correctness, but processing smaller intervals first is standard.

2. Min-Heap Initialization: Initialize a Min-Heap to store the end times of the latest interval in each group.

3. Iterate and Schedule: Loop through the sorted intervals:

   • Let the current interval be [start, end].
   • Check the heap: If the heap is not empty and the minimum value in the heap (earliest end time) is strictly less than start, it means that group is free.
   • Reuse Group: Pop the minimum element from the heap. This signifies that the previous interval in that group has finished and we are extending the group.
   • Update State: Push the current end onto the heap. Whether we reused a group or created a new one, this new end time represents the time when this specific group will next become available.

4. Result: After processing all intervals, the size of the heap represents the number of groups that were simultaneously active at peak congestion. This is our answer.

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.

Pattern Reuse Notes

The Greedy - Interval Merging/Scheduling pattern is highly versatile. Understanding the logic of sorting by start time and managing state (often with a heap or pointers) applies to:

• LeetCode 56: Merge Intervals: Instead of counting groups, we merge overlapping intervals into single continuous ranges.
• LeetCode 57: Insert Interval: A variation where we insert a new interval into a sorted list and merge if necessary.
• LeetCode 759: Employee Free Time: Uses a similar heap approach (or line sweep) to find gaps where no intervals exist.
• LeetCode 986: Interval List Intersections: Uses two pointers to find the overlapping regions between two lists of intervals.

Mastering LeetCode 2406 provides the foundation for solving these related interview questions efficiently.

Reference Implementation

C++ Solution for LeetCode 2406

1class Solution {
2public:
3    int minGroups(vector<vector<int>>& intervals) {
4        // Sort intervals by start time
5        sort(intervals.begin(), intervals.end());
6        
7        // Min-heap to store end times of the groups
8        // priority_queue is max-heap by default, so we use 'greater' for min-heap
9        priority_queue<int, vector<int>, greater<int>> pq;
10        
11        for (const auto& interval : intervals) {
12            int start = interval[0];
13            int end = interval[1];
14            
15            // If the group with the earliest end time finishes before 
16            // the current interval starts, we can reuse that group.
17            if (!pq.empty() && pq.top() < start) {
18                pq.pop();
19            }
20            
21            // Add the current interval's end time to the heap
22            // (either extending an existing group or starting a new one)
23            pq.push(end);
24        }
25        
26        // The size of the heap represents the number of active groups required
27        return pq.size();
28    }
29};

Java Solution for LeetCode 2406

1import java.util.Arrays;
2import java.util.PriorityQueue;
3
4class Solution {
5    public int minGroups(int[][] intervals) {
6        // Sort intervals by start time
7        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
8        
9        // Min-heap to store end times of active groups
10        PriorityQueue<Integer> pq = new PriorityQueue<>();
11        
12        for (int[] interval : intervals) {
13            int start = interval[0];
14            int end = interval[1];
15            
16            // If the earliest ending group finishes strictly before the current start,
17            // we can reuse that group (remove the old end time).
18            if (!pq.isEmpty() && pq.peek() < start) {
19                pq.poll();
20            }
21            
22            // Add the new end time to the heap
23            pq.offer(end);
24        }
25        
26        // The size of the heap is the minimum number of groups needed
27        return pq.size();
28    }
29}

Python Solution for LeetCode 2406

1import heapq
2
3class Solution:
4    def minGroups(self, intervals: List[List[int]]) -> int:
5        # Sort intervals by start time
6        intervals.sort()
7        
8        # Min-heap to store end times
9        min_heap = []
10        
11        for start, end in intervals:
12            # If the heap is not empty and the earliest ending group
13            # finishes before the current interval starts, reuse it.
14            if min_heap and min_heap[0] < start:
15                heapq.heappop(min_heap)
16            
17            # Push the current interval's end time
18            heapq.heappush(min_heap, end)
19            
20        # The size of the heap corresponds to the number of groups
21        return len(min_heap)