2406 Divide Intervals into Minimum Number of Groups

Problem Statement

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

Instructions

• 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.

For the whole problem statement, please refer here.

Plans

• Sort the intervals based on their starting points (and ending points to break ties).

• Use a list or priority queue to keep track of the intervales in each group.

• Itereate through the sorted intervals and determine which group the current interval can join, if any.

• If the current interval cannot join any existing group, create a new group.

• Return the length of the list or heap at the end will represent the minimum number of groups required.

Solution

from typing import List
import heapq

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

        # Initilize a min-mean to keep track of the end points of groups
        min_heap = []

        # Iterate over each interval
        for start, end in intervals:
            # If the smallest end in the heap does not overlap with the current start
            if min_heap and min_heap[0] < start:
                # Remove the smallest end point since it does not overlap with the current interval
                heapq.heappop(min_heap)

            # Add the current end point to the min-heap
            heapq.heappush(min_heap, end)
        
        # The size of the min-heap is the minimum number of groups
        return len(min_heap)

Explanation

1. Sorting Intervals

   • We begin by sortring the intervals based on their start time. This allows us to process them in the order they appear on the number line, making it easir to identify overlapping intervales. If two intervales start at the same point, we sort by their ending point as a tie-breaker.

2. Using a Min-Heap

   • A min-heap is utilized to keep track of the end points of the groups. The top of the heap represents the earliest and point of any group. This helps us quickly identify if the current interval can be added to an existing group or if a new group mush be created.

3. Iterating through Intervals

   • For each interval, we check if it starts after the earlist ending interval (the on at the top of the heap). If it does, we can pop that end time from the heap because the group that it representsed is no longer overlaps with the current interval.

4. Adding End Times to the Heap

   • Regardless of whether we popped (popped means removed) from the heap, we then push the current interval's ending time onto the healp. If no groups were available for the current interval, this effectively creates a new group.

5. Final Count of Groups

   • The number of intervals in the healp at the end is the minimum number of groups required. So each entry in the heap indicates a group that cannot overlap with any other group.