# Divide Intervals Into Minimum Number of Groups
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups)
Canonical: https://scaleengineer.com/dsa/problems/divide-intervals-into-minimum-number-of-groups
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## 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.

**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`

# Approaches
## Sorting with Min-Heap
This approach sorts the intervals by their start times and then uses a min-heap to manage the groups. The core idea is to simulate the process of assigning each interval to a group. The min-heap efficiently keeps track of the end times of the last interval in each group, allowing us to quickly find a group that an incoming interval can be placed into without causing an overlap.
**Time:** O(N log N), where N is the number of intervals. The sorting step takes O(N log N). The loop iterates through N intervals, and each heap operation (add or poll) takes O(log K) time, where K is the size of the heap (K <= N). This results in a total time complexity dominated by sorting. · **Space:** O(N), where N is the number of intervals. In the worst-case scenario, if all intervals overlap, the min-heap will need to store an end time for each interval.
**Pros:** The logic is intuitive as it directly models the process of assigning meetings to conference rooms.; It's a standard and robust technique for this class of interval problems.
**Cons:** The use of a Priority Queue can have a slightly higher constant factor overhead compared to a simple array-based sweep line approach.
### Explanation
The problem of finding the minimum number of groups for non-overlapping intervals is equivalent to finding the maximum number of intervals that overlap at any single point in time. This value is often called the "point of maximum overlap".

By sorting the intervals by their start times, we can process them chronologically. We use a min-heap to store the end times of the intervals currently assigned to groups. The value at the top of the heap represents the group that will become free the soonest.

When we consider a new interval, we check if it can be placed in any existing group. A group is available if its last interval ends before the new one begins. This corresponds to checking if the new interval's start time is greater than the smallest end time in our heap. If it is, we reuse that group by updating its end time. If not, the new interval overlaps with all currently active groups, so we must create a new group for it, which is done by adding its end time to the heap. The size of the heap at any point reflects the number of groups needed for the intervals processed so far, and its maximum size (which is its final size in this algorithm) gives the overall minimum number of groups.
### Algorithm
- Sort the `intervals` array based on their start times. This allows us to process intervals in a chronological order.
- Initialize a min-priority queue (`minHeap`) to store the end times of the intervals that are currently occupying a group. The size of the heap will represent the number of groups currently in use.
- Iterate through each sorted interval `[start, end]`:
  - Look at the top of the `minHeap`. If the heap is not empty and the current interval's `start` time is greater than the smallest end time in the heap (`minHeap.peek()`), it means we can reuse the group that finishes earliest. We do this by removing the earliest end time from the heap (`minHeap.poll()`).
  - Add the current interval's `end` time to the heap. This either places the interval into a newly freed group (the one we just polled from) or, if no group was freed, it effectively allocates a new group, increasing the heap's size.
- After iterating through all intervals, the final size of the `minHeap` is the maximum number of concurrent intervals we ever had, which corresponds to the minimum number of groups required.

## Sweep Line Algorithm with Two Pointers
A more optimized approach is the sweep-line algorithm. This method deconstructs the intervals into individual start and end points. By sorting these points, we can process them as a sequence of events. A 'start' event increases the number of active intervals, and an 'end' event decreases it. The maximum number of active intervals at any point during this 'sweep' gives us the minimum number of groups required.
**Time:** O(N log N), where N is the number of intervals. The complexity is dominated by sorting the two arrays. The subsequent two-pointer scan takes linear O(N) time. · **Space:** O(N), where N is the number of intervals, to store the separate `starts` and `ends` arrays.
**Pros:** Generally more efficient in practice due to lower overhead than heap operations.; The space complexity is straightforward (two arrays of size N).; The implementation is very concise.
**Cons:** The logic can be less intuitive to grasp at first compared to the direct simulation with a min-heap.
### Explanation
This approach elegantly calculates the maximum overlap without explicitly tracking group assignments. We create two arrays, one for all start points and one for all end points. Sorting both allows us to process events chronologically.

We use two pointers, one for the sorted `starts` and one for the sorted `ends`. We iterate through the `starts` array. For each new interval starting, we check if any interval has already ended. An interval `ends[endPointer]` has ended before `starts[startPointer]` begins if `starts[startPointer] > ends[endPointer]`. If so, a group has been freed, and we can advance our `endPointer`. The number of groups required is the total number of intervals that have started minus the number of intervals that have finished. This is tracked by `startPointer - endPointer`. The maximum value of this difference is the answer. In this specific implementation, the final result is simply `N - endPointer`.

This works because `[a, b]` and `[b, c]` are considered overlapping. Sorting the start and end points and processing them ensures that at any time `t`, a start event at `t` is processed before an end event at `t`, correctly accounting for the maximum overlap.
### Algorithm
- Create two separate integer arrays, `starts` and `ends`, each of size `N` (the number of intervals).
- Populate the `starts` array with all the start times (`left_i`) and the `ends` array with all the end times (`right_i`) from the input intervals.
- Sort both the `starts` and `ends` arrays in non-decreasing order.
- Initialize two pointers: `startPointer = 0` to iterate through `starts`, and `endPointer = 0` to iterate through `ends`.
- Iterate with `startPointer` from `0` to `N-1`:
  - For each `start` time being processed, we are essentially adding a new interval that needs a group.
  - Compare the current `starts[startPointer]` with `ends[endPointer]`. If `starts[startPointer] > ends[endPointer]`, it means the interval that ends earliest has finished before the current interval begins. This frees up a group, so we can advance `endPointer`.
  - The number of active groups at any point is `startPointer - endPointer`. Since `startPointer` always increments and `endPointer` only increments when a group is freed, the difference `startPointer - endPointer` is non-decreasing. Its maximum value will be its final value.
- The minimum number of groups is `N - endPointer` after the loop finishes.

# Solutions
### Java

```java
class Solution {
public
  int minGroups(int[][] intervals) {
    Arrays.sort(intervals, (a, b)->a[0] - b[0]);
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (var e : intervals) {
      if (!q.isEmpty() && q.peek() < e[0]) {
        q.poll();
      }
      q.offer(e[1]);
    }
    return q.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minGroups(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> q;
    for (auto &e : intervals) {
      if (q.size() && q.top() < e[0]) {
        q.pop();
      }
      q.push(e[1]);
    }
    return q.size();
  }
};

```

### Python

```python
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int: h = [] for a, b in sorted(intervals): if h and h[0] < a: heappop(h) heappush(h, b) return len(h)

```