• Leetcode POTDs

Problem 2406 Divide Intervals Into Minimum Number of Groups

Problem Statement

Link - Problem 2406

Question

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

class Solution {
public:
    int minGroups(vector<vector<int>>& inter) {
        int n = inter.size();

        sort(inter.begin(), inter.end());

        priority_queue<int, vector<int>, greater<int>> pq;

        for(int i = 0; i < n; i++) {
            int l = inter[i][0];
            int r = inter[i][1];

            if(pq.empty()){
                pq.push(r);
            }
            else{
                if(pq.top() >= l){
                    pq.push(r);
                }
                else{
                    pq.pop();
                    pq.push(r);
                }
            }
        }
        return pq.size();
    }
};

Complexity Analysis

| Algorithm                | Time Complexity | Space Complexity |
| ------------------------ | --------------- | ---------------- |
| Greedy Interval Coloring | O(n log n)      | O(n)             |

Explanation

1. Intuition

• The problem can be solved by using a greedy approach to group the intervals.
• We need to sort the intervals based on their start time to ensure that we are always considering the earliest interval first.
• We can use a priority queue to keep track of the end times of the intervals in each group.
• If the start time of the current interval is greater than or equal to the smallest end time in the priority queue, we can add the current interval to the same group.
• Otherwise, we need to create a new group for the current interval.
• The size of the priority queue at the end will give us the minimum number of groups required.
• This approach works because it ensures that we are always using the minimum number of groups required to accommodate the intervals.
• It also ensures that no two intervals in the same group intersect with each other.

2. Implementation

• We start by sorting the intervals based on their start time using sort(inter.begin(), inter.end()).
• We then initialize a priority queue pq to store the end times of the intervals in each group.
• We iterate over the sorted intervals and for each interval, we check if the priority queue is empty or if the start time of the current interval is greater than or equal to the smallest end time in the priority queue.
• If the priority queue is empty, we simply add the end time of the current interval to the queue using pq.push(r).
• If the start time of the current interval is greater than or equal to the smallest end time in the priority queue, we add the end time of the current interval to the queue using pq.push(r).
• Otherwise, we remove the smallest end time from the priority queue using pq.pop() and add the end time of the current interval to the queue using pq.push(r).
• Finally, we return the size of the priority queue using return pq.size() to get the minimum number of groups required.

Complexity Analysis

Time Complexity:

• The sorting operation sort(inter.begin(), inter.end()) dominates the time complexity, contributing O(n log n) due to the standard implementation of the sort algorithm in C++ which uses a variant of quicksort or mergesort.
• The iteration through the sorted intervals for(int i = 0; i < n; i++) contributes O(n), which is overshadowed by the sorting operation. The operations inside the loop, such as the push and pop from the priority queue pq, have a combined time complexity of O(log n) due to the use of the priority queue.
• Therefore, the overall time complexity of the algorithm is O(n log n) + O(n), which simplifies to O(n log n) because the O(n log n) term dominates for large inputs.

Space Complexity:

• The space complexity is dominated by the priority queue pq, which can store at most n intervals in the worst case. Hence, the memory usage scales linearly with the input size, resulting in O(n) space complexity.
• The input array inter is not considered in the space complexity because it’s not created by the algorithm; rather, it’s a given input.
• Thus, no additional space is allocated beyond the priority queue, leading to a space complexity of O(n).

Footnote

This question is rated as Medium difficulty.

Hints

Can you find a different way to describe the question?

The minimum number of groups we need is equivalent to the maximum number of intervals that overlap at some point. How can you find that?

Similar Questions: