Meeting Rooms

Q: What is the time complexity of Meeting Rooms?

Sorting the meetings by start time costs O(n log n) , and the walk that compares neighbors is O(n) , so the total is O(n log n) . Comparing every pair instead costs O(n²) .

Q: Why is it enough to compare each meeting with the one before it?

After sorting by start, if no clash has been found so far, the meetings so far form a chain where each one starts at or after the end of the previous one. The last one in the chain ends latest. A new meeting that starts at or after its end cannot overlap any of the earlier ones.

Q: Do meetings that touch count as overlapping?

Not in this problem: a meeting may start at the exact moment another one ends. That is why the check is a strict start < previous end . If touching meetings were forbidden, the check would become start ≤ previous end .

Q: How do you find the minimum number of meeting rooms?

Sort the start times and the end times as two separate lists, then walk both: each start opens a room and each end that comes at or before the next start frees one. The largest number of rooms open at once is the answer. Answering the yes or no question here is the same as asking whether one room is enough.

EasyIntervals Sorting

+10

You get a list of meetings as two arrays: meeting i runs from starts[i] to ends[i]. One person wants to attend all of them, so no two meetings may overlap. A meeting may start at the exact moment another one ends. Return true if the person can attend every meeting, and false otherwise.

Function

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: the start time of each meeting
endsinteger-array: the end time of each meeting, at the same index as its start
Returnsboolean: true if no two meetings overlap, false otherwise

Constraints

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
The meetings are not sorted. Two meetings may be identical.

Examples

Input: starts = [9, 13, 10]ends = [10, 15, 12]
Output: true
Explanation: In time order the meetings run from 9 to 10, 10 to 12 and 13 to 15. The second one starts the moment the first one ends, which is allowed, so the answer is true.

Input: starts = [1, 4, 7]ends = [5, 6, 8]
Output: false
Explanation: The meeting from 1 to 5 is still running at 4, when the meeting from 4 to 6 starts, so the answer is false.

+15 hidden tests on Submit

Follow-up

If meetings are booked one at a time, how would you check each new booking against the schedule in O(log n), without sorting everything again?

Solution

Checking every pair of meetings finds any clash, but it costs O(n²). Sorting by start time changes the question: a meeting can then only clash with its neighbor in the sorted order, so one comparison per meeting is enough.

Compare every pair

Correct, but does not finish on the largest tests

Intuition

Two meetings clash when each one starts before the other one ends. For meetings from 1 to 5 and from 4 to 6: 1 is before 6 and 4 is before 5, so they clash. For meetings from 9 to 10 and from 10 to 12: 10 is not before 10, so they only touch.

Using strict < on both sides is what lets a meeting start exactly when another one ends. Run the test on every pair and return false at the first clash.

The catch is the number of pairs. With n = 5000 meetings there are about 12.5 million pairs, and a schedule with no clash forces you to check all of them, which is too slow for the largest tests.

Algorithm

For every index i, and every index j after it:
If starts[i] < ends[j] and starts[j] < ends[i], the two meetings overlap: return false.
If no pair overlaps, return true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Sort by start and check neighbors

Intuition

Sort the meetings by start time, keeping each start with its own end. Now look at any meeting and the one right before it. If the earlier one ends after the later one starts, they clash. If not, the later meeting starts at or after the moment the earlier one ends.

Why is the neighbor the only meeting you need to check? If every meeting so far starts at or after the end of the one before it, the meetings so far never overlap, and the one right before is the one that ends last. A new meeting that starts at or after its end starts at or after the end of all of them.

In the first example the sorted meetings are 9 to 10, 10 to 12, 13 to 15. Start 10 is not before end 10, and start 13 is not before end 12, so there is no clash. Equal start times always clash, since every meeting lasts at least one unit, and the check catches them too.

The sort costs O(n log n) and the walk is O(n). The paired copy of the meetings takes O(n) space.

Algorithm

Pair each start with its end.
Sort the pairs by start time.
For each meeting after the first, compare its start with the end of the meeting before it.
If the start is smaller, return false.
After the loop, return true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Pitfalls and edge cases

The common bugs are about which ends get compared and how touching meetings are treated.

Sorting starts and leaving ends in the input order. Each end has to travel with its own start, or you compare a start with some other meeting's end.
Using ≤ instead of <. Meetings from 9 to 10 and from 10 to 12 touch but do not overlap, and the answer for them is true.
Checking only that each meeting ends before the next one starts in the input order. The input is not sorted, so neighbors in the input say nothing.
Writing the pair test with one condition, like starts[j] < ends[i]. It only holds up when meeting j starts later; for meetings from 5 to 6 and from 0 to 1, in that order, 0 < 6 reports a clash that is not there.

Frequently asked questions4

What is the time complexity of Meeting Rooms?

Sorting the meetings by start time costs O(n log n), and the walk that compares neighbors is O(n), so the total is O(n log n). Comparing every pair instead costs O(n²).

Why is it enough to compare each meeting with the one before it?

After sorting by start, if no clash has been found so far, the meetings so far form a chain where each one starts at or after the end of the previous one. The last one in the chain ends latest. A new meeting that starts at or after its end cannot overlap any of the earlier ones.

Do meetings that touch count as overlapping?

Not in this problem: a meeting may start at the exact moment another one ends. That is why the check is a strict start < previous end. If touching meetings were forbidden, the check would become start ≤ previous end.

How do you find the minimum number of meeting rooms?

Sort the start times and the end times as two separate lists, then walk both: each start opens a room and each end that comes at or before the next start frees one. The largest number of rooms open at once is the answer. Answering the yes or no question here is the same as asking whether one room is enough.

Python

def canAttendMeetings(starts, ends):
    # Write code here

Test cases

Case 1

Case 2

Input

starts = [9, 13, 10]
ends = [10, 15, 12]

Expected

true