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.

Method 1 — 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 2 — 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 3 — 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.