2406. 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

Approach 01:

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        // Stores the `endTimes` of intervals.
        priority_queue<int, vector<int>, greater<>> endTimeMinHeap;

        // Sort intervals by starting time.
        sort(intervals.begin(), intervals.end());

        for (const vector<int>& interval : intervals) {
            // If there's no overlap, reuse the same group by removing the earliest ending interval.
            if (!endTimeMinHeap.empty() && interval[0] > endTimeMinHeap.top())
                endTimeMinHeap.pop();
            endTimeMinHeap.push(interval[1]);
        }

        // The size of the heap represents the number of groups required.
        return endTimeMinHeap.size();
    }
};

import heapq

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        # Stores the `endTimes` of intervals.
        endTimeMinHeap = []

        # Sort intervals by starting time.
        intervals.sort()

        for interval in intervals:
            # If there's no overlap, reuse the same group by removing the earliest ending interval.
            if endTimeMinHeap and interval[0] > endTimeMinHeap[0]:
                heapq.heappop(endTimeMinHeap)
            heapq.heappush(endTimeMinHeap, interval[1])

        # The size of the heap represents the number of groups required.
        return len(endTimeMinHeap)

Time Complexity

• Sorting intervals:

  The function begins by sorting the intervals based on their starting times. This takes \(O(n \log n)\), where \(n\) is the number of intervals.

• Iterating through intervals:

  The function iterates through each interval, performing operations on a priority queue (min-heap) that stores the end times. Inserting or removing elements from the heap takes \(O(\log g)\), where \(g\) is the number of groups required. Since this operation is performed for each of the \(n\) intervals, the total complexity for this step is \(O(n \log g)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n \log n)\), where \(n\) is the number of intervals. Sorting dominates the complexity, and the heap operations contribute logarithmically with respect to the number of groups.

Space Complexity

• Auxiliary Space:

  The function uses a priority queue (min-heap) to store the end times of intervals. In the worst case, all intervals could overlap, leading to the heap storing \(n\) elements, so the space complexity is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of intervals, due to the space used by the priority queue.