Meeting Rooms II

Problem Statement

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.

Example 1:

# Definition for an interval.
class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end
intervals = [Interval(0,40),Interval(5,10),Interval(15,20)]
# Output: 2

Explanation: day1: (0,40) day2: (5,10),(15,20)

Example 2:

# Definition for an interval.
class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end
intervals = [Interval(4,9)]
# Output: 1

Note:

  • (0,8),(8,10) is not considered a conflict at 8

Constraints:

  • 0 <= intervals.length <= 500
  • 0 <= intervals[i].start < intervals[i].end <= 1,000,000

You should aim for a solution with O(n \log n) time and O(n) space, where n is the number of intervals.

Hint 1

Consider sorting the intervals by start time.

Hint 2

A min-heap can be used to keep track of the end times of the meetings in progress.

Hint 3

The sweep line algorithm can efficiently track the number of overlapping intervals.

Solution

Min Heap

import heapq


class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end


def min_meeting_rooms(intervals: list[Interval]) -> int:
    intervals.sort(key=lambda x: x.start)
    min_heap = []


    for interval in intervals:
        if min_heap and min_heap[0] <= interval.start:
            heapq.heappop(min_heap)
        heapq.heappush(min_heap, interval.end)


    return len(min_heap)

Time complexity: O(n \log n) Space complexity: O(n)