Start learning free

LESSON 350 OF 410 · GREEDY

Meeting Rooms II in Python: Minimum Rooms with Sorted Events

Practice O(n log n) Read the full explanation

Given an array consisting of meeting time intervals, which are represented by the start and end times [[s0, e0], [s1, e1], ...], determine the minimum number of meeting rooms needed in order to be able to accommodate all meetings at every moment of time.


Example:

Input: [[5, 10], [0, 30], [15, 20]]
Output: 2
Explanation: 1st and 3rd meetings can be assigned to the first room
             2nd meeting can be assigned to room 2

 

Note:

  1. You may assume the interval's end point is always greater than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap.

Your algorithm should run in O(n log n) time and use O(n) extra space.


STEP 1 OF 10
    Ctrl + Enter to check

    PYTHON · GREEDY

    Meeting Rooms in Python, explained

    Problem overview

    The method meetingRooms receives a list of meeting intervals, each written as [start, end]. It returns the minimum number of rooms needed so that every meeting has a room at every moment. A room can hold one meeting at a time. The end of every meeting is later than its start, and meetings that only touch, like [1, 2] and [2, 3], do not overlap: the second one can use the room the first just left.

    For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting [0, 30] occupies a room for its whole length, and the other two, [5, 10] and [15, 20], fit one after the other in a second room.

    The required budget is O(n log n) time and O(n) extra space.

    Approach: count how many meetings run at once

    The number of rooms needed equals the largest number of meetings in progress at any single moment. If at most three meetings ever overlap, three rooms are enough, and fewer cannot work.

    To find that maximum, turn each meeting into two events: a start at its start time and an end at its end time. Sort all events by time and sweep through them while keeping a counter. A start adds one meeting to the counter and an end removes one. The highest value the counter ever reaches is the answer.

    On the example, the sorted events are start at 0, start at 5, end at 10, start at 15, end at 20 and end at 30. The counter goes 1, 2, 1, 2, 1, 0, and its maximum is 2.

    The sort costs O(n log n) for the 2n events, and the sweep is O(n). There is also a version that sorts the meetings by start time and tracks end times in a min-heap, with the same time complexity, but the event sweep is shorter to write.

    Step by step

    1. Create an empty list events.
    2. Unpack each interval in the loop header: for start, end in intervals. Every interval has exactly two values, so Python can split it straight into two names.
    3. Append the start event [start, 1]. The 1 says that a meeting begins.
    4. Append the end event [end, -1]. The -1 says that a meeting ends. Append each pair as one element; this is a list of pairs.
    5. Sort the events with events.sort(). Python compares lists element by element, so the events are ordered by time first and, for equal times, by the second value. Since -1 is smaller than 1, an end sorts before a start at the same time. That puts the room back before the next meeting takes it, which is how touching meetings stay in one room.
    6. Start the counters. answer, noOfMeetings = 0, 0 is a tuple assignment. noOfMeetings is the number of meetings in progress and answer is the largest value seen.
    7. Loop over the sorted events, unpacking each into time and type.
    8. Update the counter. noOfMeetings += type. Because the types are +1 and -1, one addition handles both starts and ends.
    9. Track the maximum with answer = max(answer, noOfMeetings).
    10. Return answer after the loop. The maximum is only known when every event has been processed.

    The solution in Python

    class Solution:
    def meetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for start, end in intervals:
            events.append([start, 1])
            events.append([end, -1])

        events.sort()
        
        answer, noOfMeetings = 0, 0
        for time, type in events:
            noOfMeetings += type
            answer = max(answer, noOfMeetings)

        return answer

    Python details:

    • sort() works in place and returns None. Writing events = events.sort() would replace the list with None. sorted(events) returns a new list instead.
    • Naming a variable type hides the built-in type() inside the method. It is harmless because the method never calls it, but a name like delta would be safer.
    • The tie-break comes for free. Sorting lists compares [10, -1] and [10, 1] by their second elements. If you used tuples or another encoding where a start sorts first, touching meetings would count as overlapping.

    Complexity

    There are 2n events. Sorting them takes O(n log n) and the sweep takes O(n), so the time is O(n log n). The events list holds 2n small lists, so the extra space is O(n).

    Edge cases and common mistakes

    • Touching meetings. [[1, 2], [2, 3]] needs one room. The events sort as start 1, end 2, start 2, end 3, so the counter never passes 1.
    • Identical meetings. Three copies of [1, 5] need 3 rooms.
    • One meeting contains the others. [[0, 10], [2, 3], [4, 5], [6, 7]] needs only 2 rooms, because the small meetings never overlap each other.
    • No meetings. An empty list produces no events, the loop does nothing, and the result is 0.
    • Wrong order for equal times. If starts were sorted before ends at the same time, [[1, 2], [2, 3]] would give 2.
    • Returning inside the loop. That would return after the first event, with 1.

    Testing

    • [[5, 10], [0, 30], [15, 20]] returns 2.
    • [[1, 2], [2, 3]] returns 1.
    • [[1, 5], [1, 5], [1, 5]] returns 3.
    • [[7, 10]] returns 1.
    • [] returns 0.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free