Meeting Rooms II with Heaps

Find the minimum number of meeting rooms needed to schedule all meetings without overlaps.

heap intervals greedy scheduling

You are given a list of meetings, where each meeting is represented as a tuple (start, end) with start < end. All times are integers. Meetings can share a room only if their time intervals do not overlap (intervals touching at endpoints are allowed, i.e., one meeting ends exactly when another starts). Implement the function `min_meeting_rooms(meetings)` that returns the minimum number of meeting rooms required to accommodate all meetings. The list may be empty, and the ordering of meetings in the input is arbitrary. Your solution should use a heap (priority queue) to track the earliest ending meeting currently using a room.

Constraints

0 <= len(meetings) <= 10^5
For each meeting: 0 <= start < end <= 10^6
Time complexity: O(n log n) where n is the number of meetings. Space complexity: O(n).
All inputs are valid tuples of two integers, without networks or file access.

Example

>>> min_meeting_rooms([(0, 30), (5, 10), (15, 20)])
2
>>> min_meeting_rooms([(7, 10), (2, 4)])
1
>>> min_meeting_rooms([])
0

25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the meetings by start time. Then use a min-heap that stores the end times of rooms currently in use.

For each meeting in sorted order, if the earliest ending room is free (heap[0] <= start), pop it and reuse that room.

Always push the current meeting's end time onto the heap. The answer is the size of the heap after processing all meetings.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.