Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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.

Solution

Method 1 - Sorting

Here is the approach:

  1. Definition of Intersection: Two intervals [lefti, righti] and [leftj, rightj] intersect if leftj <= righti and lefti <= rightj.
  2. Greedy Approach:
    • Sort the intervals based on their start times.
    • Use a min-heap to keep track of the end times of intervals in the current groups.
    • Iterate through each interval and check if it can be placed in any of the existing groups (represented by the heap).
  3. Detailed Steps:
    1. Sort the intervals based on their start times.
    2. Initialize a min-heap to track the earliest ending interval in each group.
    3. Iterate through the sorted intervals:
      • Use the heap to check and remove any group that can accommodate the current interval.
      • Add the current interval’s end time to the heap (representing a new or extended group).
    4. The size of the heap at the end of the iteration gives the minimum number of groups required.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public int minGroups(int[][] intervals) {
        // Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // Min-heap to track the end times of the intervals in current groups
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        for (int[] interval : intervals) {
            // If the smallest end time in the heap is less than the start of current interval,
            // it means we can reuse this group
            if (!heap.isEmpty() && heap.peek() < interval[0]) {
                heap.poll(); // Remove that interval
            }
            // Add the end time of the current interval to heap
            heap.offer(interval[1]);
        }

        // The size of the heap represents the minimum number of groups
        return heap.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        # Sort intervals by start time
        intervals.sort(key=lambda x: x[0])

        # Min-heap to track the end times of the intervals in current groups
        heap = []

        for interval in intervals:
            # If the smallest end time in the heap is less than the start of current interval,
            # it means we can reuse this group
            if heap and heap[0] < interval[0]:
                heapq.heappop(heap)  # Remove that interval
            # Add the end time of the current interval to heap
            heapq.heappush(heap, interval[1])

        # The size of the heap represents the minimum number of groups
        return len(heap)

Complexity

  • ⏰ Time complexity: O(n log n) where n is the number of intervals. The sorting step takes O(n log n) time, and each heap operation (insert and extract) is O(log n), leading to a total complexity for heap operations as O(n log n).
  • 🧺 Space complexity: O(n), for storing intervals in the heap.