Meeting Rooms

Meeting Rooms is the gentlest interval question. You have a calendar of meetings. You just need to answer one yes or no question: can one person attend all of them without a clash? It sounds easy, and it is, once you sort. This question is a warm up for the harder Meeting Rooms II.

🎯 The Problem

You get a list of meetings and answer one yes or no question.

• Each meeting is a pair: a start time and an end time.
• Return true if one person can attend every meeting.
• They can attend all only if no two meetings overlap in time.
• Two meetings overlap when one starts before the other ends.
• Touching at a point is fine. A meeting ending at 30 and another starting at 30 do not clash.

Input:  intervals = [[0, 30], [5, 10], [15, 20]]
Output: false

Explanation: [0, 30] overlaps with [5, 10], so the person
cannot attend both. The answer is false.

Here is the input drawn on a number line. You can see the long [0, 30] meeting covers the times of both other meetings, so there is a clash.

So the answer is a simple true or false. True means no clashes. False means at least one clash.

🐢 Approach 1: Check Every Pair (Brute Force)

Compare every meeting against every other meeting.

The idea:

• Take each pair of meetings.
• Check if the two overlap.
• If any pair clashes, return false. If none clash, return true.

How it works:

• Two nested loops walk all pairs.
• Overlap means one starts before the other ends.

Why it is weak:

• It checks every pair, so the work is O(n²).
• A big calendar makes it slow.
• It does far more comparisons than needed.

Here is the check-every-pair code:

def can_attend_meetings(intervals):
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            a_start, a_end = intervals[i]
            b_start, b_end = intervals[j]
            if max(a_start, b_start) < min(a_end, b_end):
                return False
    return True

⚡ Approach 2: Sort Then Scan Neighbors (Best)

The idea in one line: sort by start, then a clash can only show up between neighbors.

The idea:

• Sort the meetings by start time.
• After sorting, overlaps sit right next to each other.
• So you only compare each meeting with the one before it.

How it works:

• Walk from the second meeting to the last.
• Ask: does this meeting start before the previous one ended?
• If yes, that is a clash, so return false at once.
• If you reach the end with no clash, return true.

Why it is fast:

• Sorting costs O(n log n). The single scan is O(n).
• The sort is the heavy part, so the total is O(n log n).
• No far-apart comparisons, only neighbors.

Here is the scan as a decision flow across sorted neighbors.

Steps to Solve

1. Sort the meetings by their start time.
2. Walk from the second meeting to the last.
3. For each meeting, compare its start with the end of the meeting before it.
4. If the start is less than the previous end, there is a clash, so return false.
5. If the loop finishes with no clash, return true.

#include <stdio.h>
#include <stdlib.h>

// compare by start for qsort
int cmp(const void *a, const void *b) {
    int *x = *(int **)a;
    int *y = *(int **)b;
    return x[0] - y[0];
}

int main(void) {
    int raw[][2] = {{0, 30}, {5, 10}, {15, 20}};
    int n = 3;

    int *arr[3];
    for (int i = 0; i < n; i++) arr[i] = raw[i];

    qsort(arr, n, sizeof(int *), cmp);  // sort by start

    int canAttend = 1;  // 1 means true
    for (int i = 1; i < n; i++) {
        if (arr[i][0] < arr[i - 1][1]) {  // starts before previous end
            canAttend = 0;                // clash
            break;
        }
    }

    printf("%s\n", canAttend ? "true" : "false");
    return 0;
}

false

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());  // sort by start
    for (int i = 1; i < (int)intervals.size(); i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {  // clash
            return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
    cout << (canAttendMeetings(intervals) ? "true" : "false") << endl;
    return 0;
}

false

import java.util.Arrays;

public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // sort by start
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {  // clash
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
        System.out.println(canAttendMeetings(intervals));
    }
}

false

def can_attend_meetings(intervals):
    intervals.sort(key=lambda block: block[0])  # sort by start
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:  # starts before prev end
            return False                            # clash found
    return True


intervals = [[0, 30], [5, 10], [15, 20]]
print(can_attend_meetings(intervals))

False

function canAttendMeetings(intervals) {
  intervals.sort((a, b) => a[0] - b[0]); // sort by start
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) {  // clash
      return false;
    }
  }
  return true;
}

const intervals = [[0, 30], [5, 10], [15, 20]];
console.log(canAttendMeetings(intervals));

false

Now let us walk through the Python version line by line and see why each part is written this way.

def can_attend_meetings(intervals):
    intervals.sort(key=lambda block: block[0])

We sort by block[0], the start time. This is the trick. Once meetings are in start order, a clash can only happen between a meeting and the one right before it. So we never need to compare meetings that are far apart.

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False

We loop from index 1 so we always have a previous meeting at i - 1. The check intervals[i][0] < intervals[i - 1][1] reads as “this meeting starts before the previous one ended.” That is a clash. The moment we find one clash, the answer is settled, so we return False right away and stop.

    return True

If the loop finishes with no clash, every meeting started on or after the previous one ended. So one person can attend them all. We return True. Notice we use < and not <=, because a meeting starting exactly when another ends does not clash.

⏱️ Time and Space Complexity

The brute force checks every pair, so it is O(n²). The sort then scan costs O(n log n) for the sort plus O(n) for the scan. The sort dominates, so the total is O(n log n). Space is O(1) beyond the input, since we only compare neighbors and keep no extra structure. The big idea is that sorting lets a single neighbor scan answer the whole question.

🧩 Key Takeaways

• ✅ The answer is just true or false: can one person attend every meeting?
• ✅ Sort by start, then a clash can only appear between neighbors.
• ✅ A clash means a meeting starts before the previous one ended.
• ✅ Return false on the first clash you find.
• ✅ Use strictly less than, because touching at a point is not a clash.

🚀 What’s Next?

• Meeting Rooms II
• Merge Intervals