☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Meeting Rooms

Easy TUF ID 709 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of meeting times intervals, where intervals[i] = [start_i, end_i]. Decide whether one person can attend every meeting, that is, whether no two meetings overlap.

A meeting occupies the half-open range [start, end): it is over at the moment end, so a meeting ending at 10 and another starting at 10 do not clash. The input is not sorted.

Constraints: 0 ≤ n ≤ 10^4, 0 ≤ start_i < end_i ≤ 10^6. (This is LeetCode 252, a premium problem; LintCode 920 is the same question with an Interval class instead of arrays.)

Example 1

intervals = [[0, 30], [5, 10], [15, 20]]
answer = false          // [5, 10) happens while [0, 30) is still running

Example 2

intervals = [[7, 10], [2, 4]]
answer = true           // 2-4 and then 7-10, never at the same time

Approach 1: Brute force, compare every pair

Intuition. “Can attend all” means “no pair of meetings overlaps”, so check every pair. Two half-open intervals share some moment t exactly when t is at least both starts and below both ends, so the set of shared moments is [max(starts), min(ends)). That range is non-empty precisely when max(starts) < min(ends). This one comparison covers every arrangement: partial overlap, one meeting inside another, identical meetings, and touching meetings (where max(starts) == min(ends), so no clash).

Algorithm.

  1. For every pair i < j:
    • latestStart = max(start_i, start_j) and earliestEnd = min(end_i, end_j);
    • if latestStart < earliestEnd, return false.
  2. Return true.
static boolean bruteForce(int[][] intervals) {
    int n = intervals.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int latestStart = Math.max(intervals[i][0], intervals[j][0]);
            int earliestEnd = Math.min(intervals[i][1], intervals[j][1]);
            if (latestStart < earliestEnd) return false;   // both meetings run during [latestStart, earliestEnd)
        }
    }
    return true;
}

Complexity. Time O(n^2): n(n-1)/2 pairs, each checked in constant time. Space O(1). For n = 10^4 that is 50 million checks, which is slow but survivable; for larger inputs it is not.

Approach 2: Optimal, sort by start and check neighbours

Intuition. Picture the meetings on a timeline in the order they start. If the person can attend everything, each meeting must finish before the next one in that order begins. Conversely, if every meeting finishes before the next one starts, nothing can overlap at all. So after sorting by start time, only adjacent pairs need checking: n - 1 comparisons instead of n^2 / 2.

Why neighbours are enough: suppose every adjacent pair is fine, so start[k] ≥ end[k-1] for all k in sorted order. Take any i < j. Then

start[j] ≥ end[j-1] > start[j-1] ≥ end[j-2] > ... ≥ end[i]

using end > start for every meeting along the way. So meeting j starts after meeting i ends, and no pair overlaps. Read backwards: if any two meetings overlap, some adjacent pair in sorted order overlaps, and the scan will find it.

Notice that comparing with the previous meeting’s end is enough here, even for nested meetings like [1, 10] and [2, 3]. The first clash makes us return false immediately, so we never have to remember a long meeting that is still running. Merge Intervals has to keep a running maximum end for exactly that reason, but a yes/no question does not.

Algorithm.

  1. Copy the array of intervals (to leave the caller’s order untouched) and sort the copy by start time.
  2. For i from 1 to n - 1: if start[i] < end[i-1], return false.
  3. Return true.
static boolean optimal(int[][] intervals) {
    int[][] a = intervals.clone();                         // sort a copy, keep the caller's order
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    for (int i = 1; i < a.length; i++) {
        if (a[i][0] < a[i - 1][1]) return false;           // starts before the previous meeting has ended
    }
    return true;
}

Dry run on Example 1. After sorting: [0, 30], [5, 10], [15, 20].

i meeting previous end start < previous end? result
1 [5, 10] 30 5 < 30, yes return false

On Example 2 the sorted order is [2, 4], [7, 10]; 7 < 4 is false, so the loop ends and the answer is true.

Complexity. Time O(n log n) for the sort; the scan is O(n). Space O(n) for the copied array (Java sorts object arrays with TimSort, which may also use up to O(n) scratch space). Sorting the caller’s array in place would save the copy, at the cost of changing its order.

A variant avoids sorting pairs: copy all start times into one array and all end times into another, sort both, and check starts[i] ≥ ends[i-1] for every i. If that holds, then whenever k meetings have started by time t, at least k - 1 have already ended, so at most one meeting is ever running. This is the one-room special case of the sweep used in Meeting Rooms II, and it is handy when the meetings arrive as two separate arrays of start and end times.

Edge cases and pitfalls