#66 · Intervals

Meeting Rooms

Given meeting time intervals [start, end), determine whether one person could attend all of them (no two overlap).

EasyLeetCode

Being examined
New / inserted
Kept / merged / answer
Removed / conflict
Untouched

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sorted order of starts

If the meetings are sorted by start time and some pair overlaps, then a pair of neighbours overlaps. So the whole question reduces to comparing each meeting with the one before it.

Memory layout

An array of intervals, sorted in place or copied.

Operation	Cost
time	O(n log n)
space	O(1) to O(n) depending on the sort

Separate sorted starts and ends

The pairing of start and end does not matter for counting how many meetings are running at once: sort the two lists independently and compare the i-th start with the (i−1)-th end.

Memory layout

Two integer arrays.

Operation	Cost
time / space	O(n log n) / O(n)

Why it fits

Overlap is a local relation once meetings are in time order: a meeting can only clash with the one that starts just before it, or with something that also clashes with that one.
Meetings are half-open ([start, end)), so one that starts exactly when another ends does not clash, which fixes the comparison as < not <=.
Counting concurrency (starts versus ends) generalises directly to the next problem, how many rooms are needed.

Why alternatives degrade

Checking every pair:: Correct but O(n²), and it ignores that sorting makes the question local.
Timeline of minutes:: Works for small times, but costs the total length of all meetings and the size of the time range.
Sorting by end time only:: It also works (check each start against the previous end), but sorting by start is the natural order for most interval problems.

Four approaches, from naive to production

1 · beginner

Compare every pair

time O(n²)space O(1)

For every pair of meetings test whether they overlap (each starts before the other ends). If any pair does, the person cannot attend them all.

bool canAttendMeetings(vector<vector<int>>& intervals) {
    for (size_t i = 0; i < intervals.size(); i++) {
        for (size_t j = i + 1; j < intervals.size(); j++) {
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
        }
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    for (int i = 0; i < intervals.length; i++) {
        for (int j = i + 1; j < intervals.length; j++) {
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
        }
    }
    return true;
}

def can_attend_meetings(intervals):
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  for (let i = 0; i < intervals.length; i++) {
    for (let j = i + 1; j < intervals.length; j++) {
      if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
    }
  }
  return true;
}

Flaws & bottlenecks

Quadratic number of comparisons.
Ignores order: neighbours in time are the only pairs that matter.
The overlap test needs both comparisons; testing only one gives wrong answers.

Interviewer cross-questions

Why two comparisons in the overlap test?

Say: Intervals A and B overlap exactly when A starts before B ends AND B starts before A ends. One comparison alone would also accept disjoint intervals.

Do meetings that touch overlap?

Say: No. With half-open [start, end) meetings, one that ends at 10 and another that starts at 10 are fine, so the comparisons are strict.

How do you avoid checking all pairs?

Say: Sort by start: only consecutive meetings can be the first to clash.

2 · intermediate

Sort by start, compare neighbours

time O(n log n)space O(n) for the copy

Sort the meetings by start time and check that each meeting starts no earlier than the previous one ends.

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

public boolean canAttendMeetings(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] < sorted[i - 1][1]) return false;
    }
    return true;
}

def can_attend_meetings(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] < sorted_iv[i - 1][1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < sorted[i - 1][1]) return false;
  }
  return true;
}

Flaws & bottlenecks

The sort costs more than the single pass that follows.
Copying before sorting protects the caller's array but allocates.
An empty or single-meeting list must return true (the loop simply does not run).

Interviewer cross-questions

Why are neighbours enough after sorting?

Say: If meeting k overlaps some later meeting m, then m starts before k ends, and any meeting between them starts even earlier, so k also overlaps its immediate successor.

What would you return for an empty list?

Say: true: with no meetings there is nothing to clash with.

Can you do better than sorting?

Say: Not in general: detecting an overlap is as hard as element distinctness, which needs Ω(n log n) comparisons. A bounded time range allows a linear timeline method.

3 · advanced

Mark busy minutes on a timeline

time O(total duration + range)space O(range)

When times are small integers, allocate a boolean array for the time range, mark every minute each meeting uses, and report a clash as soon as a minute is marked twice.

bool canAttendMeetings(vector<vector<int>>& intervals) {
    int maxTime = 0;
    for (auto& iv : intervals) maxTime = max(maxTime, iv[1]);
    vector<bool> busy(maxTime, false);
    for (auto& iv : intervals) {
        for (int t = iv[0]; t < iv[1]; t++) {
            if (busy[t]) return false;
            busy[t] = true;
        }
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    int maxTime = 0;
    for (int[] iv : intervals) maxTime = Math.max(maxTime, iv[1]);
    boolean[] busy = new boolean[maxTime];
    for (int[] iv : intervals) {
        for (int t = iv[0]; t < iv[1]; t++) {
            if (busy[t]) return false;
            busy[t] = true;
        }
    }
    return true;
}

def can_attend_meetings(intervals):
    max_time = 0
    for iv in intervals: max_time = max(max_time, iv[1])
    busy = [False] * max_time
    for start, end in intervals:
        for t in range(start, end):
            if busy[t]: return False
            busy[t] = True
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  let maxTime = 0;
  for (const [, end] of intervals) maxTime = Math.max(maxTime, end);
  const busy = new Array<boolean>(maxTime).fill(false);
  for (const [start, end] of intervals) {
    for (let t = start; t < end; t++) {
      if (busy[t]) return false;
      busy[t] = true;
    }
  }
  return true;
}

Flaws & bottlenecks

Cost depends on the total length of the meetings and the time range, not on n.
Impossible for large or fractional times (timestamps in milliseconds).
Allocates an array as long as the latest end time.

Interviewer cross-questions

When is this better than sorting?

Say: When the time range is small and there are very many meetings (for example minute-granularity scheduling within a day). It is linear and needs no sort.

Why does a clash show up as a repeated minute?

Say: Two meetings overlap exactly when they share at least one minute of time, so a minute marked by two meetings is a witness.

How would you scale it to big timestamps?

Say: Coordinate compression: map the distinct start and end times to a small range first. That is another sort, so you might as well use the sort-based method.

4 · expert

Sorted starts against sorted ends

time O(n log n)space O(n)

Sort the start times and the end times independently. If the i-th start is before the (i−1)-th end, at least two meetings are running at once, so return false.

bool canAttendMeetings(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& iv : intervals) { starts.push_back(iv[0]); ends.push_back(iv[1]); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    for (size_t i = 1; i < starts.size(); i++) {
        if (starts[i] < ends[i - 1]) return false;
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    for (int i = 1; i < n; i++) {
        if (starts[i] < ends[i - 1]) return false;
    }
    return true;
}

def can_attend_meetings(intervals):
    starts = sorted(x[0] for x in intervals)
    ends = sorted(x[1] for x in intervals)
    for i in range(1, len(starts)):
        if starts[i] < ends[i - 1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  const starts = intervals.map((x) => x[0]).sort((a, b) => a - b);
  const ends = intervals.map((x) => x[1]).sort((a, b) => a - b);
  for (let i = 1; i < starts.length; i++) {
    if (starts[i] < ends[i - 1]) return false;
  }
  return true;
}

Flaws & bottlenecks

The pairing between starts and ends is lost, which makes the argument less intuitive.
Two sorted copies need more memory than sorting the intervals.
It only detects a clash; it does not say which meetings clash.

Interviewer cross-questions

Why can you sort starts and ends separately?

Say: Only the number of meetings running at a moment matters, not which ones. Every moment is a start (count up) or an end (count down), and those two sorted lists carry all of that information.

Why does starts[i] < ends[i - 1] mean an overlap?

Say: By the time the i-th meeting begins, i + 1 meetings have started (indices 0…i), but at most i − 1 have finished (ends 0…i−2 are the earliest possible). So at least two are running.

How does it extend to the next problem?

Say: Meeting Rooms II asks for the maximum number running at once, which the same two sorted lists give with two pointers.

Synchronized code walkthrough

Showing: Compare every pair — shares the player above; click any step to jump.

bool canAttendMeetings(vector<vector<int>>& intervals) {
    for (size_t i = 0; i < intervals.size(); i++) {
        for (size_t j = i + 1; j < intervals.size(); j++) {
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
        }
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    for (int i = 0; i < intervals.length; i++) {
        for (int j = i + 1; j < intervals.length; j++) {
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
        }
    }
    return true;
}

def can_attend_meetings(intervals):
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  for (let i = 0; i < intervals.length; i++) {
    for (let j = i + 1; j < intervals.length; j++) {
      if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) return false;
    }
  }
  return true;
}

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

public boolean canAttendMeetings(int[][] intervals) {
    int[][] sorted = intervals.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] < sorted[i - 1][1]) return false;
    }
    return true;
}

def can_attend_meetings(intervals):
    sorted_iv = sorted(intervals, key=lambda p: p[0])
    for i in range(1, len(sorted_iv)):
        if sorted_iv[i][0] < sorted_iv[i - 1][1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] < sorted[i - 1][1]) return false;
  }
  return true;
}

bool canAttendMeetings(vector<vector<int>>& intervals) {
    int maxTime = 0;
    for (auto& iv : intervals) maxTime = max(maxTime, iv[1]);
    vector<bool> busy(maxTime, false);
    for (auto& iv : intervals) {
        for (int t = iv[0]; t < iv[1]; t++) {
            if (busy[t]) return false;
            busy[t] = true;
        }
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    int maxTime = 0;
    for (int[] iv : intervals) maxTime = Math.max(maxTime, iv[1]);
    boolean[] busy = new boolean[maxTime];
    for (int[] iv : intervals) {
        for (int t = iv[0]; t < iv[1]; t++) {
            if (busy[t]) return false;
            busy[t] = true;
        }
    }
    return true;
}

def can_attend_meetings(intervals):
    max_time = 0
    for iv in intervals: max_time = max(max_time, iv[1])
    busy = [False] * max_time
    for start, end in intervals:
        for t in range(start, end):
            if busy[t]: return False
            busy[t] = True
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  let maxTime = 0;
  for (const [, end] of intervals) maxTime = Math.max(maxTime, end);
  const busy = new Array<boolean>(maxTime).fill(false);
  for (const [start, end] of intervals) {
    for (let t = start; t < end; t++) {
      if (busy[t]) return false;
      busy[t] = true;
    }
  }
  return true;
}

bool canAttendMeetings(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& iv : intervals) { starts.push_back(iv[0]); ends.push_back(iv[1]); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    for (size_t i = 1; i < starts.size(); i++) {
        if (starts[i] < ends[i - 1]) return false;
    }
    return true;
}

public boolean canAttendMeetings(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    for (int i = 1; i < n; i++) {
        if (starts[i] < ends[i - 1]) return false;
    }
    return true;
}

def can_attend_meetings(intervals):
    starts = sorted(x[0] for x in intervals)
    ends = sorted(x[1] for x in intervals)
    for i in range(1, len(starts)):
        if starts[i] < ends[i - 1]: return False
    return True

function canAttendMeetings(intervals: number[][]): boolean {
  const starts = intervals.map((x) => x[0]).sort((a, b) => a - b);
  const ends = intervals.map((x) => x[1]).sort((a, b) => a - b);
  for (let i = 1; i < starts.length; i++) {
    if (starts[i] < ends[i - 1]) return false;
  }
  return true;
}