Divide Intervals Into Minimum Number of Groups

Problem Statement

In the given problem, you are provided with a two-dimensional integer array named intervals, where each sub-array intervals[i] = [lefti, righti] characterizes an interval ranging from lefti to righti inclusively. The task is to organize these intervals into several distinct groups. Each group must consist of intervals that do not overlap with one another, where two intervals are considered overlapping if they share at least one common number. The primary challenge is to determine the minimal number of such groups required to successfully and completely separate all the provided intervals without any intersections within the same group.

Examples

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 and Intuition

The core challenge in this problem involves efficiently grouping intervals such that no two intervals in the same group intersect, and simultaneously minimizing the total number of such groups. The problem narrows down to a classic scenario of interval scheduling and graph coloring. Here's an intuitive approach broken down into actionable steps:

1. Sort the intervals by their starting point. This step aids in a sequential processing where we can manage overlaps as they appear.
2. Utilize a priority queue (or similar data structure) to keep track of the end times of intervals in current active groups.
3. For each interval in the sorted list:
   • Check the group (or the interval in the priority queue) that finishes the earliest (has the smallest end time).
   • If the interval does not overlap with this earliest finishing interval, add it to the same group (i.e., update the end time in the priority queue).
   • If it does overlap, create a new group for this interval, represented by adding a new end time to the priority queue.
4. The size of the priority queue at the end of the iterations will give the minimal number of groups required as it reflects the number of concurrent non-overlapping intervals at any point in the process.

This approach leverages the greedy technique of interval scheduling wherein we aim to optimally use the minimal number of resources (groups, in this case) by orderly and strategically processing and placing each interval. This method ensures both completeness (every interval is in some group) and minimalism (minimal groups formed) in forming the interval groups.

Solutions

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        // Determine smallest and largest interval bounds
        int minIntervalStart = INT_MAX;
        int maxIntervalEnd = INT_MIN;
        for (vector<int> interval : intervals) {
            minIntervalStart = min(minIntervalStart, interval[0]);
            maxIntervalEnd = max(maxIntervalEnd, interval[1]);
        }
    
        // Build a difference array for interval counts
        vector<int> countDifferences(maxIntervalEnd + 2, 0);
        for (vector<int> interval : intervals) {
            countDifferences[interval[0]]++;
            countDifferences[interval[1] + 1]--;
        }
    
        int activeIntervals = 0;
        int maximumOverlap = 0;
        for (int i = minIntervalStart; i <= maxIntervalEnd; i++) {
            // Compute current active intervals
            activeIntervals += countDifferences[i];
            maximumOverlap = max(maximumOverlap, activeIntervals);
        }
    
        return maximumOverlap;
    }
};