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 costs O(n²) .

Q: Do meetings that touch count as overlapping?

Not in this problem: a meeting may start at the exact moment another one ends, so the check is a strict start < previous end . If touching meetings were forbidden, it 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 at or before the next start frees one. The largest number of rooms open at once is the answer. This problem asks 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 starts the moment the first 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.

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 in O(n²). Sort by start time instead: 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 starts before the other ends: for 1 to 5 and 4 to 6, 1 is before 6 and 4 is before 5. Strict < on both sides lets 9 to 10 and 10 to 12 touch without clashing. Test every pair and return false at the first clash.

With n = 5000 there are about 12.5 million pairs, and a schedule with no clash makes you check them all.

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. If no clash has turned up so far, the meetings so far form a chain, each starting at or after the end of the one before. So the meeting right before the new one ends last, and a new meeting that starts at or after its end overlaps none of them. One that starts before it clashes.

Equal starts always clash, since every meeting lasts at least one unit, and the same check catches them. The sort costs O(n log n), the walk O(n), and the paired copy of the meetings 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

Sorting starts and leaving ends in the input order. Each end must travel with its own start, or you compare a start with another meeting's end.
Using ≤ instead of <. Meetings from 9 to 10 and 10 to 12 only touch, and the answer for them is true.
Comparing neighbors in the input order. The input is not sorted: 1 to 5, 7 to 8, 4 to 6 has no clash between neighbors, yet the first and last overlap.
Writing the pair test with one condition, like starts[j] < ends[i]. For meetings from 5 to 6 and 0 to 1, in that order, 0 < 6 reports a clash that is not there.

Frequently asked questions3

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 costs O(n²).

Do meetings that touch count as overlapping?

Not in this problem: a meeting may start at the exact moment another one ends, so the check is a strict start < previous end. If touching meetings were forbidden, it 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 at or before the next start frees one. The largest number of rooms open at once is the answer. This problem asks whether one room is enough.

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

Test #1

Test #2

Arguments

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

Expected Output

true