Meeting Rooms

The problem

You are given a list intervals of n meetings (n is the length of intervals), each as [start, end]. Return true if one person can attend all of them, meaning no two meetings share any time. A meeting that ends at 4 and one that starts at 4 do not clash.

Example 1

Input: intervals = [[7, 10], [2, 4], [11, 13], [4, 6], [14, 15]]

Output: true

In time order: 2 to 4, 4 to 6, 7 to 10, 11 to 13, 14 to 15. No two overlap.

meetings

Example 2

Input: intervals = [[1, 5], [8, 9], [3, 7]]

Output: false

[3, 7] starts at 3, while [1, 5] is still running.

Example 3

Input: intervals = []

Output: true

No meetings, so nothing can clash.

Constraints

• 0 ≤ n ≤ 10,000
• 0 ≤ start < end ≤ 1,000,000

Clarifying questions

Is back to back a clash?

No. If one meeting ends at 4 and the next starts at 4, both can be attended.

Are the meetings sorted?

No. They come in any order.

Can the list be empty?

Yes. Then the answer is true.

Do we need to find the clash?

No, only whether one exists.

Spot the pattern

A list of time ranges and a question about overlaps: that is the intervals pattern. Its first move is nearly always to sort by start. Once sorted, the meetings line up in time, and a clash must show up between two meetings that sit next to each other.

Solutions

Check every pairO(n²)Sort, check neighborsO(n log n)

Show all

This problem has two approaches. Once the meetings are sorted, one pass is all that is left.

Check every pair O(n²)

The idea

Compare every pair of meetings. Two meetings first and second clash when each starts before the other ends: first.start < second.end and second.start < first.end. If any pair clashes, return false. If none does, return true.

It is correct, because it looks at every pair. But n meetings make about n² / 2 pairs.

Walkthrough

meetings

pairs checked

0

1. for i in range(len(intervals)):
2. for j in range(i + 1, len(intervals)):
3. first, second = intervals[i], intervals[j]
4. if first[0] < second[1] and second[0] < first[1]:
5. return False
6. return True

Compare every pair of meetings. Two meetings clash when each one starts before the other ends.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Check every pair: two meetings clash when each starts before the other ends.
    // About n * n / 2 pairs, so O(n^2) time and O(1) memory.
    public boolean canAttendMeetings(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                int[] first = intervals[i], second = intervals[j];
                // Strict <: back to back meetings do not clash.
                if (first[0] < second[1] && second[0] < first[1]) return false;
            }
        }
        return true;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines compare one pair. They sit inside two loops. Two comparisons are 1 step.

   1. for i in range(len(intervals)):
   2. for j in range(i + 1, len(intervals)):
   3. first, second = intervals[i], intervals[j]
   4. if first[0] < second[1] and second[0] < first[1]:
   5. return False
   6. return True

2. 2 Count the runs on Example 1

   Example 1 has 5 meetings and no clash, so every pair is checked: 4 for the first meeting, 3 for the second, and so on.

   4 + 3 + 2 + 1 = 10 checks.

   i	0	1	2	3	4
   pairs	4	3	2	1	0

   total

   4 + 3 + 2 + 1 = 10

3. 3 Write the count for any n

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2

   Check it with Example 1: 5 × 4 / 2 = 10.

4. 4 Keep only the part that grows fastest

   Drop the ½ and the −½n. What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps i and j. The space is O(1).

   ij

Sort, check neighbors O(n log n)

The idea

Sort the meetings by start. Then walk them once and compare each meeting with the one just before it. If a meeting starts before the previous one ends, there is a clash.

Why checking neighbors is enough: say meeting j clashes with some earlier meeting i. Every meeting between them starts at or after i starts and no later than j starts, which is before i ends. So i also clashes with the meeting right after it. A clash anywhere means a clash between neighbors.

Walkthrough

meetings

1. intervals.sort(key=lambda interval: interval[0])
2. for i in range(1, len(intervals)):
3. if intervals[i][0] < intervals[i - 1][1]:
4. return False
5. return True

Unsorted, a clash could hide between any two meetings.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort, check neighbors: once sorted by start, any clash shows up between two
    // meetings next to each other. The sort costs O(n log n), the check O(n).
    public boolean canAttendMeetings(int[][] intervals) {
        java.util.Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
        for (int i = 1; i < intervals.length; i++) {
            // Strict <: a meeting may start exactly when the last one ends.
            if (intervals[i][0] < intervals[i - 1][1]) return false;
        }
        return true;
    }
}

Big O

Time O(n log n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The sort compares meetings many times. Then the loop does one comparison per meeting, which is 1 step per run.

   1. intervals.sort(key=lambda interval: interval[0])
   2. for i in range(1, len(intervals)):
   3. if intervals[i][0] < intervals[i - 1][1]:
   4. return False
   5. return True

2. 2 Count the runs on Example 1

   Example 1 has 5 meetings. Sorting 5 items takes about 5 × log₂ 5, so about 12 steps. Then 4 neighbor checks.

   12 + 4 = about 16 steps.

   part	sort	neighbor checks
   steps	about 5 × log 5 ≈ 12	4

3. 3 Write the count for any n

   n log₂ n (sort) + (n − 1) (checks)

   Check it with Example 1: 5 × 2.3 + 4 ≈ 16.

4. 4 Keep only the part that grows fastest

   Keep the sort. log n keeps growing, so n log n pulls away from the n − 1 checks. What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The loop keeps only i. Sorting in place needs little extra memory, though some languages use up to O(n) for it. Beyond the sort, the space is O(1).

   isort space

Common mistake

Using ≤ for the clash test

intervals[i][0] <= intervals[i - 1][1] calls back to back meetings a clash, so [2, 4] and [4, 6] would wrongly return false. A meeting must start strictly before the last one ends to clash.

Tested at the limits

2,000 random lists of 0 to 5 meetings with times from 0 to 10, so back-to-back meetings, clashes and empty lists all come up. Check every pair and sort, check neighbors gave the same answer every time.

Largest inputs	Result
10,000 meetings (the most allowed), back to back and shuffled, so no clash and every neighbor pair is checked. Sort, check neighbors.	0.003 s, and about 0.15 MB of extra memory, all for the sort. The check itself keeps two numbers.
2,000 meetings. Check every pair, about 2 million pairs.	0.13 s. At 10,000 meetings it would check 50 million pairs.