2406. Divide Intervals Into Minimum Number of Groups

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

2406. Divide Intervals Into Minimum Number of Groups

Difficulty: Medium

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 <= 10⁵
intervals[i].length == 2
1 <= lefti <= righti <= 10⁶

Hint:

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?

Solution:

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:

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.

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.
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) {
        ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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:

Events Array: We build an array of events where each interval contributes two events ([start, +1] and [end+1, -1]).
Sorting: We sort these events. When two events have the same time, we prioritize ending intervals (-1) over starting intervals (+1).
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).
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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

Print Share Comment Cite Upload Translate Updates

APA

MD ARIFUL HAQUE | Sciencx (2024-10-12T22:41:26+00:00) 2406. Divide Intervals Into Minimum Number of Groups. Retrieved from https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/

MLA

" » 2406. Divide Intervals Into Minimum Number of Groups." MD ARIFUL HAQUE | Sciencx - Saturday October 12, 2024, https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/

HARVARD

MD ARIFUL HAQUE | Sciencx Saturday October 12, 2024 » 2406. Divide Intervals Into Minimum Number of Groups., viewed ,<https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/>

VANCOUVER

MD ARIFUL HAQUE | Sciencx - » 2406. Divide Intervals Into Minimum Number of Groups. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/

CHICAGO

" » 2406. Divide Intervals Into Minimum Number of Groups." MD ARIFUL HAQUE | Sciencx - Accessed . https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/

IEEE

" » 2406. Divide Intervals Into Minimum Number of Groups." MD ARIFUL HAQUE | Sciencx [Online]. Available: https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/. [Accessed: ]

rf:citation

» 2406. Divide Intervals Into Minimum Number of Groups | MD ARIFUL HAQUE | Sciencx | https://www.scien.cx/2024/10/12/2406-divide-intervals-into-minimum-number-of-groups/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Explanation:

Approach:

Explanation of the Code:

Complexity:

Related Posts