We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Divide Intervals Into Minimum Number of Groups

Difficulty: Medium

Problem Description

You are given a 2D integer array intervals where intervals[i] = [left_i, right_i] represents the inclusive interval [left_i, right_i]. 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.

Key Insights

  • Intervals can be represented by their start and end points.
  • Sorting the intervals by their start points allows us to easily manage overlapping intervals.
  • A greedy approach can be used to assign intervals to groups based on their end points.
  • A min-heap (or priority queue) can efficiently keep track of the end points of current groups to determine if a new interval can be added to an existing group or if a new group is needed.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the intervals. Space Complexity: O(n) - for the min-heap that stores the end points of the groups.

Solution

To solve this problem, we can follow these steps:

  1. Sort the intervals based on their start points.
  2. Use a min-heap to track the end points of the groups.
  3. Iterate through each interval:
    • If the starting point of the current interval is greater than the smallest end point in the heap, we can merge this interval into that group (remove the smallest end point from the heap).
    • Add the current interval's end point to the heap.
  4. The size of the heap at the end will give us the minimum number of groups required.

Code Solutions

import heapq

def minGroups(intervals):
    # Sort intervals by starting point
    intervals.sort(key=lambda x: x[0])
    min_heap = []  # Min-heap to track the end points

    for interval in intervals:
        # If the current interval starts after the earliest end point, pop from heap
        if min_heap and interval[0] > min_heap[0]:
            heapq.heappop(min_heap)
        # Add the current interval's end point to the heap
        heapq.heappush(min_heap, interval[1])
    
    # The size of the heap is the number of groups required
    return len(min_heap)
← Back to All Questions