Start learning free

LESSON 355 OF 415 · GREEDY

Meeting Rooms in Swift: O(n log n) with Sorted Start and End 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

    SWIFT · GREEDY

    Meeting Rooms in Swift, explained

    Problem overview

    The method meetingRooms receives intervals, an array of [start, end] pairs, one per meeting. It returns the smallest number of rooms that lets every meeting happen without two meetings sharing a room at the same moment. Each end is greater than its start. Two meetings that merely touch, such as [1, 2] and [2, 3], don't overlap and can use the same room.

    Take [[5, 10], [0, 30], [15, 20]]. The meeting [0, 30] runs the whole time, and the other two never overlap each other. One room holds [5, 10] and then [15, 20], a second room holds [0, 30], so the answer is 2.

    The statement asks for O(n log n) time and O(n) extra space.

    Approach: count the meetings running at once

    The number of rooms needed equals the largest number of meetings in progress at any single moment. Comparing every pair of meetings to find that would take O(n²) work. A faster way is to stop thinking about meetings and think about events instead.

    Every meeting produces two events: a start, which adds one running meeting, and an end, which removes one. Put all the events in time order and walk through them while keeping a running count. The highest value the count ever reaches is the answer.

    Sorting costs O(n log n) and the walk is a single pass, so the total fits the budget. The events array holds 2n pairs, which is O(n) space.

    When a start and an end share the same time, the order matters. If a meeting ends at 10 and another starts at 10, the first one should be processed first. Its room is free by the time the second one needs it, and the count never rises to 2 for them. Tagging starts with 1 and ends with -1 gives the rule for free: sorting by time and then by tag puts -1 before 1.

    Step by step

    1. Create an empty list of events. It is a var of type [[Int]] because the loop appends to it, and each event is a small [time, type] array.
    2. Loop over intervals. Each element is one meeting.
    3. Append the start event [interval[0], 1]. The tag 1 means one more meeting is running.
    4. Append the end event [interval[1], -1]. The tag -1 means one fewer.
    5. Sort the events in place by time, breaking ties so that -1 comes before 1. An array of Int arrays has no built-in ordering in Swift, so the sort needs a closure that says when the first event comes first.
    6. Declare the two counters, answer and noOfMeetings, both starting at 0. The first holds the best value seen so far, the second the number of meetings running right now.
    7. Loop over the sorted events.
    8. Add the event's tag to the running count. Because the tags are 1 and -1, one addition handles both kinds of event.
    9. Keep the maximum. After each update, answer becomes the larger of itself and the current count.
    10. Return answer after the loop. The peak is known only after every event has been processed.

    The solution in Swift

    class Solution {
    func meetingRooms(_ intervals: [[Int]]) -> Int {
        var events = [[Int]]()
        for interval in intervals {
            events.append([interval[0], 1])
            events.append([interval[1], -1])
        }

        events.sort { a, b in
            if a[0] == b[0] { return a[1] < b[1] }
            return a[0] < b[0]
        }

        var answer = 0, noOfMeetings = 0
        for event in events {
            noOfMeetings += event[1]
            answer = max(answer, noOfMeetings)
        }

        return answer
    }
}

    The Swift details worth a closer look:

    • The sort closure. sort with a trailing closure takes two elements and returns true when the first must come before the second. Here a and b are both [Int] events. The closure has several statements, so Swift needs the explicit return keywords.
    • sort versus sorted. sort reorders events in place, which is why it must be a var. sorted would return a new array and leave the original untouched.
    • [[Int]](). This calls the initializer of an array of integer arrays and gives an empty one. Writing var events: [[Int]] = [] means the same.
    • One var, two names. var answer = 0, noOfMeetings = 0 declares both variables in a single statement.
    • Global max. Swift has a free function max(_:_:) that returns the larger of two comparable values.
    • Value semantics. The intervals parameter is never modified. The events are new arrays, so the caller's data stays as it was.

    Complexity

    Time: O(n log n). Building the events takes O(n), sorting 2n events takes O(n log n), and the final loop is O(n). The sort dominates.

    Space: O(n). The events array stores two small arrays per meeting. The sort works in place on that array, and the counters take constant space.

    Edge cases and common mistakes

    • Touching meetings. [[1, 2], [2, 3]] returns 1. At time 2 the end (-1) sorts before the start (1), so the count goes 1, 0, 1, 0 and never reaches 2.
    • No meetings. An empty array gives no events, the second loop never runs, and the method returns 0.
    • Everything overlaps. [[1, 5], [2, 6], [3, 7]] returns 3.
    • Ties sorted the other way. If starts came before ends at equal times, [[1, 2], [2, 3]] would report 2 rooms. The tie-break line is what makes the touching rule work.
    • Sorting only by time. The order of equal-time events would then be arbitrary, and the answer could change for the worse.
    • Unsorted input. Meetings can arrive in any order. [[7, 10], [2, 4]] returns 1. The sort is what makes the running count meaningful.
    • Returning inside the loop. The peak is only known once every event has been seen.

    Testing

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