Meeting Rooms

NeetCode: Meeting Rooms · LeetCode: 252. Meeting Rooms · Difficulty: Easy

You are given an array of meeting time intervals [start, end] with start < end. Return true if one person can attend all of them, meaning no two meetings overlap. A meeting that ends at time t does not conflict with one that starts at t.

Example

Text

Input:  intervals = [[0,30],[5,10],[15,20]]    Output: false    ([0,30] overlaps the others)
Input:  intervals = [[5,8],[9,15]]             Output: true

Brute force: compare every pair

Two meetings a and b overlap when each starts before the other ends: a.start < b.end && b.start < a.end. Check all pairs.

Java

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                int[] a = intervals[i];
                int[] b = intervals[j];
                if (a[0] < b[1] && b[0] < a[1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canAttendMeetings(new int[][] {{0, 30}, {5, 10}, {15, 20}}));
        System.out.println(solution.canAttendMeetings(new int[][] {{5, 8}, {9, 15}}));
        System.out.println(solution.canAttendMeetings(new int[][] {{1, 5}, {5, 8}}));
        System.out.println(solution.canAttendMeetings(new int[][] {}));
    }
}

Output

false
true
true
true

Time: O(n^2). Space: O(1).

Optimal: sort by start, check neighbours

If any two meetings overlap, then after sorting by start time some adjacent pair overlaps too: the meeting that starts right after the first one begins before the first one ends. So sort and only compare each meeting's start with the previous meeting's end.

Java

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i - 1][1] > sorted[i][0]) {
                return false;
            }
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canAttendMeetings(new int[][] {{0, 30}, {5, 10}, {15, 20}}));
        System.out.println(solution.canAttendMeetings(new int[][] {{5, 8}, {9, 15}}));
        System.out.println(solution.canAttendMeetings(new int[][] {{1, 5}, {5, 8}}));
        System.out.println(solution.canAttendMeetings(new int[][] {}));
    }
}

Output

false
true
true
true

intervals.clone() copies the outer array so the sort does not reorder the caller's data. An empty or one-element array skips the loop and returns true. Time: O(n log n). Space: O(n) for the sorted copy.