Medium

Divide Intervals Into Minimum Number of Groups

LAB

Given inclusive intervals, return the minimum number of groups needed so intervals in each group do not overlap.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      5,
      10
    ],
    [
      6,
      8
    ],
    [
      1,
      5
    ],
    [
      2,
      3
    ],
    [
      1,
      10
    ]
  ]
}

Output
3

FUNCTION SHAPE

intervals: intMatrix→int

SOLUTION NOTE

Key insight: The minimum number of groups needed equals the maximum number of overlapping intervals at any point, which we can efficiently calculate using line sweep.

This is exactly the same as meeting rooms 2, the only difference is we need to subtract 1 at e+1 instead of e. This is because: "Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect."

Reveal reference solution +

pythonREFERENCE

# Heap solution (same as Meeting Rooms II)
def minGroups(self, intervals: List[List[int]]) -> int:
    intervals.sort()
    group_end_times = []

    for s, e in intervals:
        if group_end_times and s > group_end_times[0]:
            heappop(group_end_times)
        heappush(group_end_times, e)

    return len(group_end_times)

# Line sweep solution
def minGroups(self, intervals: List[List[int]]) -> int:
    lines = defaultdict(int)

    for s, e in intervals:
        lines[s] += 1
        lines[e+1] -= 1

    res = 0
    sum_ = 0
    for t in sorted(lines):
        sum_ += lines[t]
        res = max(res, sum_)

    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗