Meeting Rooms 1 - Can person attend all meetings

Problem

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

Examples

Example 1:

Input: intervals = [(0,30),(5,10),(15,20)]
Output: false
Explanation: 
(0,30), (5,10) and (0,30),(15,20) will conflict

Solution

There are a few standard ways to decide if a single person can attend all meetings. All approaches detect whether any two intervals overlap; if so, return false. It is very similar to [Check if Intervals Overlap](check-if-intervals-overlap). Some edge cases, to consider when designing the solution:

• Empty list or single interval → true.
• Touching intervals like [1,2] and [2,3] are allowed (no overlap) — ensure sort/tie-breakers treat end == start as non-overlapping.
• Intervals with invalid input (start >= end) should be validated depending on problem constraints.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/KWT_l6ssYQg" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Naive

Intuition

The problem asks if any meetings in a given list overlap. If we can find even one pair of meetings that conflict, the answer is false. If no pairs conflict, the answer is true.

The core of the problem is how to efficiently detect an overlap. A brute-force approach would be to compare every meeting with every other meeting, but this is inefficient. A more insightful approach is to realize that if we process the meetings in the order they are supposed to start, we can detect conflicts much more easily.

If we sort the meetings by their start times, any potential conflict will always be between a meeting and the one that starts immediately after it. We only need to check if a meeting starts before the previous one has ended.

Approach

1. Iterate through each meeting: Use a nested loop. The outer loop picks a meeting (i).
2. Compare with every other meeting: The inner loop picks another meeting (j).
3. Check for overlap: For each pair of meetings, check if their time intervals overlap. An overlap occurs if the start time of one meeting is before the end time of the other, and vice-versa.
4. Return false on overlap: If an overlap is found, we can immediately return false.
5. Return true if no overlaps: If the loops complete without finding any overlaps, it means no meetings conflict, and we can return true.

Complexity

• ⏰ Time complexity: O(n^2). We compare each of the n meetings with n other meetings.
• 🧺 Space complexity: O(1). No extra space is used.

Method 2 — Sort by start time

Intuition

Sort intervals by start time and scan left-to-right; a meeting that starts before the previous meeting ends causes a conflict. Example: [(0,30),(5,10)] fails because 5 < 30.

Approach

1. If the list is empty return true.
2. Sort intervals by their start time.
3. Let prev be the end time of the first interval.
4. For each following interval (s,e):
   • If s < prev there is an overlap → return false.
   • Otherwise set prev = e and continue.
5. If the loop finishes, return true.

Code

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return true;
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b){
      if (a[0] != b[0]) return a[0] < b[0];
      return a[1] < b[1];
    });
    int prev = intervals[0][1];
    for (size_t i = 1; i < intervals.size(); ++i) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
};

Go

package main

import "sort"

func canAttendMeetings(intervals [][]int) bool {
  if len(intervals) == 0 {
    return true
  }
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  prev := intervals[0][1]
  for i := 1; i < len(intervals); i++ {
    if intervals[i][0] < prev {
      return false
    }
    prev = intervals[i][1]
  }
  return true
}

Java

import java.util.*;

class Solution {
  public boolean canAttendMeetings(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return true;
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    int prev = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
}

Kotlin

class Solution {
  fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
    if (intervals.isEmpty()) return true
    intervals.sortWith(compareBy({ it[0] }, { it[1] }))
    var prev = intervals[0][1]
    for (i in 1 until intervals.size) {
      if (intervals[i][0] < prev) return false
      prev = intervals[i][1]
    }
    return true
  }
}

Python

class Solution:
  def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
    if not intervals:
      return True
    intervals.sort(key=lambda x: x[0])
    prev: int = intervals[0][1]
    for s, e in intervals[1:]:
      if s < prev:
        return False
      prev = e
    return True

Rust

impl Solution {
  pub fn can_attend_meetings(mut intervals: Vec<Vec<i32>>) -> bool {
    if intervals.is_empty() { return true; }
    intervals.sort_by(|a, b| a[0].cmp(&b[0]));
    let mut prev = intervals[0][1];
    for i in 1..intervals.len() {
      if intervals[i][0] < prev { return false; }
      prev = intervals[i][1];
    }
    true
  }
}

TypeScript

class Solution {
  public canAttendMeetings(intervals: number[][]): boolean {
    if (!intervals || intervals.length === 0) return true;
    intervals.sort((a, b) => a[0] - b[0]);
    let prev = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
}

Complexity

• ⏰ Time complexity: O(n log n), sorting dominates; scan is O(n).
• 🧺 Space complexity: O(n) worst-case for sorting (depends on language and sort implementation) or O(1) extra aside from input.

Method 3 — Sort by end time

Intuition

If intervals are ordered by end time, checking that each next meeting starts after the previous end detects overlaps; ordering by end time is useful when choosing non-overlapping intervals.

Approach

1. Return true on empty input.
2. Sort intervals by their end time.
3. Track prev = end time of first interval.
4. For each subsequent (s,e):
   • If s < prev return false.
   • Update prev = e.
5. Return true.

Code

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return true;
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b){
      if (a[1] != b[1]) return a[1] < b[1];
      return a[0] < b[0];
    });
    int prev = intervals[0][1];
    for (size_t i = 1; i < intervals.size(); ++i) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
};

Go

package main

import "sort"

func canAttendMeetingsByEnd(intervals [][]int) bool {
  if len(intervals) == 0 { return true }
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
  prev := intervals[0][1]
  for i := 1; i < len(intervals); i++ {
    if intervals[i][0] < prev { return false }
    prev = intervals[i][1]
  }
  return true
}

Java

import java.util.*;

class Solution {
  public boolean canAttendMeetings(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return true;
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int prev = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
}

Kotlin

class Solution {
  fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
    if (intervals.isEmpty()) return true
    intervals.sortWith(compareBy({ it[1] }, { it[0] }))
    var prev = intervals[0][1]
    for (i in 1 until intervals.size) {
      if (intervals[i][0] < prev) return false
      prev = intervals[i][1]
    }
    return true
  }
}

Python

class Solution:
  def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
    if not intervals: return True
    intervals.sort(key=lambda x: x[1])
    prev: int = intervals[0][1]
    for s, e in intervals[1:]:
      if s < prev: return False
      prev = e
    return True

Rust

impl Solution {
  pub fn can_attend_meetings_by_end(mut intervals: Vec<Vec<i32>>) -> bool {
    if intervals.is_empty() { return true; }
    intervals.sort_by(|a, b| a[1].cmp(&b[1]));
    let mut prev = intervals[0][1];
    for i in 1..intervals.len() {
      if intervals[i][0] < prev { return false; }
      prev = intervals[i][1];
    }
    true
  }
}

TypeScript

class Solution {
  public canAttendMeetings(intervals: number[][]): boolean {
    if (!intervals || intervals.length === 0) return true;
    intervals.sort((a, b) => a[1] - b[1]);
    let prev = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
      if (intervals[i][0] < prev) return false;
      prev = intervals[i][1];
    }
    return true;
  }
}

Complexity

• ⏰ Time complexity: O(n log n), sorting by end dominates; linear scan afterwards.
• 🧺 Space complexity: O(n) worst-case due to sorting or O(1) extra.

Method 4 — Sweep line (events)

Intuition

Convert intervals into start/end events and scan time-ordered events; if more than one meeting is active at any point, there is a conflict. Treat an end at time t as happening before a start at t to allow touching intervals.

Approach

1. Build an events list with (time, delta) where delta = +1 for start and -1 for end.
2. Sort events by (time, delta) so that end events come before start events at the same time.
3. Sweep through events accumulating active += delta; if active > 1 return false.
4. If sweep finishes, return true.

Code

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
    std::vector<std::pair<int,int>> events;
    for (auto &it : intervals) {
      events.emplace_back(it[0], 1);
      events.emplace_back(it[1], -1);
    }
    std::sort(events.begin(), events.end(), [](const auto& a, const auto& b){
      if (a.first != b.first) return a.first < b.first;
      return a.second < b.second; // end(-1) before start(+1)
    });
    int active = 0;
    for (auto &e : events) {
      active += e.second;
      if (active > 1) return false;
    }
    return true;
  }
};

Go

package main

import "sort"

func canAttendMeetingsEvents(intervals [][]int) bool {
  events := make([][2]int, 0, len(intervals)*2)
  for _, it := range intervals {
    events = append(events, [2]int{it[0], 1})
    events = append(events, [2]int{it[1], -1})
  }
  sort.Slice(events, func(i, j int) bool {
    if events[i][0] != events[j][0] { return events[i][0] < events[j][0] }
    return events[i][1] < events[j][1]
  })
  active := 0
  for _, ev := range events {
    active += ev[1]
    if active > 1 { return false }
  }
  return true
}

Java

import java.util.*;

class Solution {
  public boolean canAttendMeetings(int[][] intervals) {
    List<int[]> events = new ArrayList<>();
    for (int[] it : intervals) {
      events.add(new int[]{it[0], 1});
      events.add(new int[]{it[1], -1});
    }
    events.sort((a, b) -> {
      if (a[0] != b[0]) return a[0] - b[0];
      return a[1] - b[1];
    });
    int active = 0;
    for (int[] e : events) {
      active += e[1];
      if (active > 1) return false;
    }
    return true;
  }
}

Kotlin

class Solution {
  fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
    val events = mutableListOf<Pair<Int, Int>>()
    for (it in intervals) {
      events.add(Pair(it[0], 1))
      events.add(Pair(it[1], -1))
    }
    events.sortWith(compareBy({ it.first }, { it.second }))
    var active = 0
    for ((_, d) in events) {
      active += d
      if (active > 1) return false
    }
    return true
  }
}

Python

class Solution:
  def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
    events: list[tuple[int,int]] = []
    for s, e in intervals:
      events.append((s, 1))
      events.append((e, -1))
    events.sort(key=lambda x: (x[0], x[1]))
    active: int = 0
    for _, d in events:
      active += d
      if active > 1:
        return False
    return True

Rust

impl Solution {
  pub fn can_attend_meetings_events(intervals: Vec<Vec<i32>>) -> bool {
    let mut events: Vec<(i32,i32)> = Vec::with_capacity(intervals.len()*2);
    for it in intervals {
      events.push((it[0], 1));
      events.push((it[1], -1));
    }
    events.sort_by(|a,b| if a.0 != b.0 { a.0.cmp(&b.0) } else { a.1.cmp(&b.1) });
    let mut active = 0;
    for (_t, d) in events {
      active += d;
      if active > 1 { return false; }
    }
    true
  }
}

TypeScript

class Solution {
  public canAttendMeetings(intervals: number[][]): boolean {
    const events: [number, number][] = [];
    for (const it of intervals) {
      events.push([it[0], 1]);
      events.push([it[1], -1]);
    }
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    let active = 0;
    for (const [, d] of events) {
      active += d;
      if (active > 1) return false;
    }
    return true;
  }
}

Complexity

• ⏰ Time complexity: O(n log n) for sorting events and O(n) sweep.
• 🧺 Space complexity: O(n) for the event list.