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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Divide Intervals Into Minimum Number of Groups

Number: 2488

Difficulty: Medium

Paid? No

Companies: Google, IBM, Adobe, Walmart Labs

Problem Description

Given an array of intervals where each interval is defined as [left, right] (inclusive), the goal is to partition these intervals into the minimum number of groups such that no two intervals in the same group intersect. Two intervals intersect if they share at least one common number.

Key Insights

  • The minimum number of groups required is equivalent to the maximum number of overlapping intervals at any point in time.
  • By processing the intervals using a sweep line technique (or sorted endpoints), one can track how many intervals are active concurrently.
  • Sorting the start and end points separately (or handling them as events) allows for efficient counting of overlaps.
  • Greedy decisions based on interval endpoints eliminate unnecessary overlaps in groups.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting of events. Space Complexity: O(n) for storing the events.

Solution

The solution uses a sweep line algorithm. First, transform the intervals into two events per interval (one for the start and one for the end). Sort these events such that when a start and an end event coincide, the start event is processed first (because [a, b] overlaps with an interval beginning at b). As you iterate over these events, maintain a counter for active intervals. The maximum counter value observed is the minimum number of groups needed since it represents the worst-case scenario of concurrent overlapping intervals.

Alternatively, a min-heap (priority queue) can also be used:

  • Sort intervals by their starting point.
  • Use the heap to store the end points of intervals currently in a group.
  • For each interval, if the heap’s smallest end point is less than the current interval’s start, you can reuse that group (pop from heap) and push the new end. Otherwise, allocate a new group (push the new end).
  • The size of the heap at the end is the number of groups needed.

Both approaches yield O(n log n) time complexity.

Code Solutions

# Python solution using the Sweep Line technique

def min_groups(intervals):
    events = []
    # Create events: (+1) for interval start, (-1) for interval end + 1 since end is inclusive.
    for left, right in intervals:
        events.append((left, 1))      # Start of an interval increases active count
        events.append((right + 1, -1))  # End + 1 decreases active count
    
    # Sort events first by time; if tie, events with smaller delta come first.
    # Note: (right+1, -1) comes after (right, 1) if both exist at same time.
    events.sort()
    
    max_groups = 0
    current_active = 0
    for time, delta in events:
        current_active += delta
        max_groups = max(max_groups, current_active)
    return max_groups

# Example test
intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
print(min_groups(intervals))  # Expected output: 3
← Back to All Questions