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 <= 105intervals[i].length == 21 <= lefti <= righti <= 106This approach involves sorting intervals by starting times and then greedily finding the minimum number of groups. When an interval starts after the end of another interval, they can be in the same group; otherwise, they need different groups.
The key insight is to manage the end times of groups using a priority queue (or a min-heap).
The implementation sorts intervals based on the start time, uses the endTimes array to track end times of intervals in each group, and iteratively places each interval in the earliest non-overlapping group. If no such group is available, a new one is created.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing end times.
This approach uses a sweep line algorithm where events are created for interval starts and ends. By tracking a count of ongoing intervals, the maximum number of overlapping intervals at any point can be determined, which corresponds to the minimum number of groups required.
It effectively converts the problem into finding the peak number of overlapping intervals.
The solution creates events for the start and the end (incremented by 1 for exclusive end point) of each interval. It sorts these events and uses a counter to track ongoing intervals, updating the maximum overlap found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) for sorting events.
Space Complexity: O(n), events list.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Interval Grouping | Time Complexity: O(n log n), due to sorting. Space Complexity: O(n), for storing end times. |
| Approach 2: Sweep Line Algorithm | Time Complexity: O(n log n) for sorting events. Space Complexity: O(n), events list. |
Divide Intervals Into Minimum Number of Groups - Leetcode 2406 - Python • NeetCodeIO • 11,302 views views
Watch 9 more video solutions →Practice Divide Intervals Into Minimum Number of Groups with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor