Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Intervals

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
[1,3]
[8,10]
[2,6]
[15,18]

Unsorted intervals. Sort by start first.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easyintervals

Meeting Rooms

Problem (restated)

Given meeting intervals [start, end], return whether a person can attend all of them (no two meetings overlap). Touching endpoints (end == next.start) is allowed.

Intuition

If any two meetings overlap, sorting by start surfaces the conflict as an adjacent pair.

Approaches

Sort by start + adjacent check

Tested only
Time O(n log n)Space O(1) or O(n)

Idea. Sort by start. For each consecutive pair, if next.start < prev.end, there is a conflict.

Walkthrough. [[0,30],[5,10],[15,20]] → after sort, 5 < 30 → false. [[7,10],[2,4]] → sorted [[2,4],[7,10]] → 7 ≥ 4 → true.

Trade-offs. Sorting is the bottleneck. Sweep-line with events also works and generalizes to Meeting Rooms II.

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

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

Template connection

Detect-overlap sibling of Merge Intervals. Same sort-then-scan skeleton; early exit on first conflict.

Reflection