2406. Divide Intervals Into Minimum Number of Groups

[mah-shamim]

Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum

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

Hint:

1. Can you find a different way to describe the question?
2. 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?

[kovatz]

To solve the problem of dividing intervals into the minimum number of groups such that no two intervals in the same group intersect, we can interpret it in a different way:

Explanation:

The minimum number of groups needed is equivalent to the maximum number of intervals that overlap at any point in time. This approach is based on the fact that if multiple intervals overlap at a particular point, each one will require a separate group.

Approach:

1. Sorting Events: We can convert each interval into two events:

   • A start event (+1) at the left point.
   • An end event (-1) at the right + 1 point (to ensure the interval is closed).

   These events will help track when intervals start and stop overlapping.

2. Sweep Line Algorithm: Using a sweep line approach:

   • Sort all events based on their time.
   • Use a counter to track the number of ongoing intervals at each point.
   • Keep track of the maximum count of overlapping intervals as we process each event.

3. Result: The maximum count of overlapping intervals at any point is the minimum number of groups required.

Let's implement this solution in PHP: 2406. Divide Intervals Into Minimum Number of Groups

<?php
/**
 * @param Integer[][] $intervals
 * @return Integer
 */
function minGroups($intervals) {
    $events = [];

    // Convert intervals into start and end events
    foreach ($intervals as $interval) {
        $events[] = [$interval[0], 1];     // +1 for start of an interval
        $events[] = [$interval[1] + 1, -1]; // -1 for end of an interval (right+1 to make it inclusive)
    }

    // Sort events based on time, and prioritize end (-1) over start (+1) if times are equal
    usort($events, function($a, $b) {
        if ($a[0] == $b[0]) {
            return $a[1] - $b[1];
        }
        return $a[0] - $b[0];
    });

    $maxGroups = 0;
    $currentGroups = 0;

    // Process the events
    foreach ($events as $event) {
        $currentGroups += $event[1];
        $maxGroups = max($maxGroups, $currentGroups);
    }

    return $maxGroups;
}

// Example usage:
$intervals1 = [[5, 10], [6, 8], [1, 5], [2, 3], [1, 10]];
echo minGroups($intervals1); // Output: 3

$intervals2 = [[1, 3], [5, 6], [8, 10], [11, 13]];
echo minGroups($intervals2); // Output: 1
?>

Explanation of the Code:

1. Events Array: We build an array of events where each interval contributes two events ([start, +1] and [end+1, -1]).
2. Sorting: We sort these events. When two events have the same time, we prioritize ending intervals (-1) over starting intervals (+1).
3. Sweep Line Processing: We iterate through sorted events, adjusting the currentGroups as intervals start or end:
   • Increment for +1 (start of an interval).
   • Decrement for -1 (end of an interval).
4. Track Maximum: The maxGroups stores the peak number of simultaneous overlapping intervals, which is our answer.

Complexity:

• Time Complexity: O(n log n) due to sorting of events.
• Space Complexity: O(n) for storing the events.

This solution efficiently determines the minimum number of groups required by finding the peak number of overlapping intervals.

[mah-shamim]

Thanks to solve the problem of dividing intervals into the minimum number of groups such that no two intervals in the same group intersect

[kovatz]

Thanks