Meeting Rooms (LC 252): Sort by Start Time

Decide whether one person can attend every meeting, given start and end times. Sort meetings by start time and check that each one starts no earlier than the previous one ends. O(n log n) time.

Language Selection

Choose your preferred programming language

Showing: Python

Meeting Rooms

Problem Statement

You are given a list of meetings, intervals, where each entry [start, end] gives a meeting’s start and end time, with start < end. A single person wants to attend all of them, and can only be in one meeting at a time.

Return true if no two meetings overlap, and false otherwise. A meeting that ends at the same moment another begins does not conflict with it: someone can leave a meeting ending at 10 and join one starting at 10.

Examples

Example 1:

Input: intervals = [[9,11],[13,15],[11,13]]
Output: true
Explanation: In time order the meetings are [9,11], [11,13], [13,15]. Each one starts exactly when the previous one ends.

Example 2:

Input: intervals = [[1,6],[8,12],[5,9]]
Output: false
Explanation: [5,9] starts before [1,6] has ended (and also overlaps [8,12]).

Example 3:

Input: intervals = []
Output: true
Explanation: With no meetings there is nothing to conflict.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i < end_i <= 10^6

Approach 1: Compare Every Pair

Algorithm

Two meetings a and b overlap exactly when each one starts before the other ends: a.start < b.end and b.start < a.end. Check that condition for every pair.

  1. For each pair i < j, test whether meetings i and j overlap.
  2. If any pair overlaps, return false.
  3. If no pair does, return true.

Implementation

Python:

from typing import List


class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        n = len(intervals)
        for i in range(n):
            for j in range(i + 1, n):
                # Overlap: each meeting starts before the other one ends
                if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                    return False
        return True

Java:

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Overlap: each meeting starts before the other one ends
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Go:

func canAttendMeetings(intervals [][]int) bool {
    n := len(intervals)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            // Overlap: each meeting starts before the other one ends
            if intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1] {
                return false
            }
        }
    }
    return true
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @return {boolean}
 */
var canAttendMeetings = function(intervals) {
    const n = intervals.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // Overlap: each meeting starts before the other one ends
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                return false;
            }
        }
    }
    return true;
};

C#:

public class Solution {
    public bool CanAttendMeetings(int[][] intervals) {
        int n = intervals.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Overlap: each meeting starts before the other one ends
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        size_t n = intervals.size();
        for (size_t i = 0; i < n; i++) {
            for (size_t j = i + 1; j < n; j++) {
                // Overlap: each meeting starts before the other one ends
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

Complexity Analysis

  • Time: O(n^2). There are n(n - 1) / 2 pairs.
  • Space: O(1).

Approach 2: Sort by Start Time (Optimal)

Algorithm

After sorting by start time, it is enough to compare each meeting with the one just before it. One pass over adjacent pairs answers the question.

  1. Sort the meetings by start time.
  2. For each i from 1 to n - 1, if intervals[i].start < intervals[i - 1].end, return false.
  3. Return true.

Why adjacent pairs are enough: if every adjacent pair is fine, the meetings form a chain where each ends no later than the next starts, so no two meetings anywhere in the chain overlap. If some pair overlaps, some adjacent pair overlaps too: suppose meeting a overlaps a later-starting meeting b. If no adjacent pair between them conflicted, each meeting from a to b would end no later than the next one starts, so a would end no later than b starts, a contradiction. The conflicting adjacent pair may not be a and b themselves, as in [[1,10],[2,3],[5,6]], but the check still finds one.

Implementation

Python:

from typing import List


class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda m: m[0])  # earliest start first
        for i in range(1, len(intervals)):
            # Starts before the previous meeting has ended: conflict
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True

Java:

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // earliest start first
        for (int i = 1; i < intervals.length; i++) {
            // Starts before the previous meeting has ended: conflict
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

Go:

import "sort"

func canAttendMeetings(intervals [][]int) bool {
    // Earliest start first
    sort.Slice(intervals, func(a, b int) bool { return intervals[a][0] < intervals[b][0] })
    for i := 1; i < len(intervals); i++ {
        // Starts before the previous meeting has ended: conflict
        if intervals[i][0] < intervals[i-1][1] {
            return false
        }
    }
    return true
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @return {boolean}
 */
var canAttendMeetings = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]); // earliest start first
    for (let i = 1; i < intervals.length; i++) {
        // Starts before the previous meeting has ended: conflict
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }
    return true;
};

C#:

using System;

public class Solution {
    public bool CanAttendMeetings(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0])); // earliest start first
        for (int i = 1; i < intervals.Length; i++) {
            // Starts before the previous meeting has ended: conflict
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

C++:

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

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        // Earliest start first
        sort(intervals.begin(), intervals.end(),
             [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
        for (size_t i = 1; i < intervals.size(); i++) {
            // Starts before the previous meeting has ended: conflict
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

Complexity Analysis

  • Time: O(n log n) for the sort. The scan is O(n).
  • Space: O(1) extra besides the sort’s own working memory (O(log n) for C++ std::sort and C# Array.Sort, up to O(n) for Python’s Timsort and Java’s object sort).

Key Insights

  1. Sorting turns a pairwise question into a neighbor question: once meetings are in start order, only adjacent meetings need comparing.
  2. Back-to-back is allowed: the conflict test is a strict start < previousEnd. A meeting starting exactly when the previous ends is fine.
  3. The overlap test for two intervals is a.start < b.end && b.start < a.end. It covers every case: partial overlap, one inside the other, and identical meetings.
  4. This is the yes/no version of Meeting Rooms II: asking “do we need more than one room?” is the same as asking whether any two meetings overlap.

Edge Cases

  1. No meetings or one meeting: always true.
  2. Back-to-back meetings: [[5,10],[10,15]] returns true, in either input order.
  3. Identical meetings: [[3,7],[3,7]] returns false.
  4. One meeting inside another: [[1,10],[2,3]] returns false. Sorting puts [1,10] first, and 2 < 10 catches it.
  5. Unsorted input: [[10,15],[5,10]] must be sorted first. Checking the input order directly would compare the wrong neighbors.

Common Mistakes

  1. Using <= for the conflict check: that reports back-to-back meetings as conflicts.
  2. Skipping the sort: adjacent checks only work on meetings in start order.
  3. Sorting by end and comparing starts incorrectly: sorting by end also works if you check start[i] < end[i - 1], but mixing the sort key and the comparison is a common source of bugs. Pick one and reason it through.
  4. Comparator subtraction in Java: a[0] - b[0] is safe for these bounds, but Integer.compare avoids overflow for arbitrary ints.
  5. Forgetting the empty list: loops starting at index 1 handle it naturally. Code that reads intervals[0] first does not.

Interview Tips

  1. Clarify the boundary rule up front: ask whether a meeting ending at 10 conflicts with one starting at 10. Here it does not.
  2. Mention the brute force in one line: then move to sorting. The interviewer mainly wants to see the adjacent-pair argument.
  3. Explain why adjacent comparisons are enough: it is the core of the answer and takes two sentences.
  4. Expect Meeting Rooms II next: be ready to count the minimum rooms with a min-heap of end times or two sorted arrays.

Follow-up Questions

  1. How many rooms are needed? That is Meeting Rooms II (LC 253). Sort by start and keep a min-heap of end times, or sweep sorted start and end arrays. O(n log n).
  2. Return the conflicting pair? During the scan, the first i that fails gives the pair (i - 1, i) in sorted order. Sort indices instead of intervals to report original positions.
  3. Meetings arrive one at a time? Keep the booked meetings in a balanced tree keyed by start. For each new meeting, check only its predecessor and successor, O(log n) per booking (LC 729, My Calendar I).
  4. Minimum meetings to cancel so the rest fit? That is Non-overlapping Intervals: greedy by earliest end time.