{x}
blog image

Divide Intervals Into Minimum Number of Groups

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

 

Example 1:

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Explanation: 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
Explanation: 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 Explanation: Divide Intervals Into Minimum Number of Groups

This problem asks to find the minimum number of groups needed to divide a set of intervals such that no two intervals within the same group overlap. The optimal approach leverages a greedy strategy combined with a priority queue (min-heap).

Algorithm:

  1. Sort: Sort the intervals by their starting times (left endpoints). This ensures we process intervals in increasing order of their start times.

  2. Priority Queue (Min-Heap): Use a min-heap data structure to track the ending times (right endpoints) of the intervals currently assigned to different groups. The min-heap's minimum element always represents the earliest ending time among all active groups.

  3. Iterate and Assign: Iterate through the sorted intervals:

    • Check for Overlap: If the current interval's starting time is greater than or equal to the minimum ending time in the heap (heap's top element), it means the current interval can be safely added to the group represented by that ending time. Remove the minimum ending time (top of the heap) and insert the current interval's ending time into the heap. This essentially reassigns the group's ending time.
    • No Overlap Possible: If the current interval's starting time is less than the minimum ending time in the heap, it indicates that the current interval cannot be added to any existing group without causing overlap. Therefore, create a new group for this interval and add its ending time to the heap.

  4. Result: Finally, the size of the min-heap represents the minimum number of groups required. Each element in the heap corresponds to a group, and its value is the right endpoint of the last interval added to that group.

Time Complexity: O(N log N) - dominated by sorting the intervals. The heap operations (insertion, deletion, peek) take logarithmic time.

Space Complexity: O(N) - proportional to the maximum size of the heap (worst case, all intervals might end up in separate groups).

Code Examples (Python):

import heapq
 
def minGroups(intervals):
    intervals.sort()  # Sort by start times
    min_heap = []  # Min-heap to track ending times of groups
    for start, end in intervals:
        if min_heap and min_heap[0] <= start:  # Check for overlap
            heapq.heapreplace(min_heap, end)  # Replace the earliest ending time
        else:
            heapq.heappush(min_heap, end)  # Create a new group
    return len(min_heap)  # Number of groups is the heap size
 
#Example Usage
intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
result = minGroups(intervals)
print(f"Minimum Number of Groups: {result}") # Output: 3
 
intervals = [[1,3],[5,6],[8,10],[11,13]]
result = minGroups(intervals)
print(f"Minimum Number of Groups: {result}") # Output: 1

The code in other languages (Java, C++, Go, TypeScript) would follow a very similar structure, utilizing their respective sorting and priority queue implementations. The core logic remains the same, making it efficient and effective for solving the problem.