252. Meeting Rooms - Explanation

Description

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), determine if a person could add all meetings to their schedule without any conflicts.

Note: (0,8),(8,10) is not considered a conflict at 8

Example 1:

Input: intervals = [(0,30),(5,10),(15,20)]

Output: false

Explanation:

(0,30) and (5,10) will conflict
(0,30) and (15,20) will conflict

Example 2:

Input: intervals = [(5,8),(9,15)]

Output: true

Constraints:

0 <= intervals.length <= 500
0 <= intervals[i].start < intervals[i].end <= 1,000,000

Topics

Array Sorting

Recommended Time & Space Complexity

You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.

Hint 1

If two intervals are sorted in ascending order by their start values, they overlap if the start value of the second interval is less than the end value of the first interval. And these are called overlapping intervals.

Hint 2

A brute force approach would be to check every pair of intervals and return false if any overlap is found. This would be an O(n^2) solution. Can you think of a better way? Maybe you should visualize the given intervals as line segments.

Hint 3

We should sort the given intervals based on their start values, as this makes it easier to check for overlaps by comparing adjacent intervals. We then iterate through the intervals from left to right and return false if any adjacent intervals overlap.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Required to process meetings in order and enable efficient overlap detection
Intervals - Understanding how to represent and compare time intervals
Overlap Detection - Knowing how to determine if two intervals share common time

1. Brute Force

Intuition

We want to check whether a person can attend all meetings without any overlap.

Two meetings overlap if they share any common time.
For two intervals A and B, this happens when:

the earlier ending time is greater than the later starting time

In a brute force approach, we simply:

compare every pair of meetings
if any pair overlaps, it is impossible to attend all meetings

This approach is very straightforward and easy to understand, making it ideal as a starting solution.

Algorithm

Let n be the number of meetings.
For each meeting i from 0 to n - 1:
Compare it with every meeting j where j > i:
For meetings A and B:
- Check if they overlap using:
  - min(A.end, B.end) > max(A.start, B.start)
If an overlap is found:
- return false immediately
If no overlapping pair is found after checking all pairs:
- return true

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        n = len(intervals)
        for i in range(n):
            A = intervals[i]
            for j in range(i + 1, n):
                B = intervals[j]
                if min(A.end, B.end) > max(A.start, B.start):
                    return False
        return True

/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    public boolean canAttendMeetings(List<Interval> intervals) {
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            Interval A = intervals.get(i);
            for (int j = i + 1; j < n; j++) {
                Interval B = intervals.get(j);
                if (Math.min(A.end, B.end) > Math.max(A.start, B.start)) {
                    return false;
                }
            }
        }
        return true;
    }
}

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            Interval& A =intervals[i];
            for (int j = i + 1; j < n; j++) {
                Interval& B =intervals[j];
                if (min(A.end, B.end) > max(A.start, B.start)) {
                    return false;
                }
            }
        }
        return true;
    }
};

/**
 * Definition of Interval:
 * class Interval {
 *   constructor(start, end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

class Solution {
    /**
     * @param {Interval[]} intervals
     * @returns {boolean}
     */
    canAttendMeetings(intervals) {
        const n = intervals.length;
        for (let i = 0; i < n; i++) {
            const A = intervals[i];
            for (let j = i + 1; j < n; j++) {
                const B = intervals[j];
                if (Math.min(A.end, B.end) > Math.max(A.start, B.start)) {
                    return false;
                }
            }
        }
        return true;
    }
}

/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    public bool CanAttendMeetings(List<Interval> intervals) {
        int n = intervals.Count;
        for (int i = 0; i < n; i++) {
            Interval A = intervals[i];
            for (int j = i + 1; j < n; j++) {
                Interval B = intervals[j];
                if (Math.Min(A.end, B.end) > Math.Max(A.start, B.start)) {
                    return false;
                }
            }
        }
        return true;
    }
}

/**
 * Definition of Interval:
 * type Interval struct {
 *    start int
 *    end   int
 * }
 */

func canAttendMeetings(intervals []Interval) bool {
    n := len(intervals)
    for i := 0; i < n; i++ {
        A := intervals[i]
        for j := i + 1; j < n; j++ {
            B := intervals[j]
            if min(A.end, B.end) > max(A.start, B.start) {
                return false
            }
        }
    }
    return true
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

/**
 * Definition of Interval:
 * class Interval(var start: Int, var end: Int) {}
 */

class Solution {
    fun canAttendMeetings(intervals: List<Interval>): Boolean {
        val n = intervals.size
        for (i in 0 until n) {
            val A = intervals[i]
            for (j in i + 1 until n) {
                val B = intervals[j]
                if (minOf(A.end, B.end) > maxOf(A.start, B.start)) {
                    return false
                }
            }
        }
        return true
    }
}

/**
 * Definition of Interval:
 * class Interval {
 *     var start: Int
 *     var end: Int
 *     init(start: Int, end: Int) {
 *         self.start = start
 *         self.end = end
 *     }
 * }
 */

class Solution {
    func canAttendMeetings(_ intervals: [Interval]) -> Bool {
        let n = intervals.count
        for i in 0..<n {
            let A = intervals[i]
            for j in (i + 1)..<n {
                let B = intervals[j]
                if min(A.end, B.end) > max(A.start, B.start) {
                    return false
                }
            }
        }
        return true
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Sorting

Intuition

We want to determine whether a person can attend all meetings without any overlaps.

A key observation is:

if meetings are sorted by their start time, then
we only need to check adjacent meetings for overlap

Why this works:

if two meetings overlap, they must appear next to each other after sorting by start time
there is no need to compare every pair

So by sorting once and doing a single pass, we can efficiently detect any conflict.

Algorithm

Sort all meetings by their start time.
Iterate through the sorted list starting from the second meeting:
For each pair of adjacent meetings:
- let i1 be the previous meeting
- let i2 be the current meeting
If i1.end > i2.start:
- the meetings overlap
- return false
If the loop finishes without finding any overlap:
- return true

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        intervals.sort(key=lambda i: i.start)

        for i in range(1, len(intervals)):
            i1 = intervals[i - 1]
            i2 = intervals[i]

            if i1.end > i2.start:
                return False
        return True

/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    public boolean canAttendMeetings(List<Interval> intervals) {
        Collections.sort(intervals, Comparator.comparingInt(i -> i.start));

        for (int i = 1; i < intervals.size(); i++) {
            Interval i1 = intervals.get(i - 1);
            Interval i2 = intervals.get(i);

            if (i1.end > i2.start) {
                return false;
            }
        }

        return true;
    }
}

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& x, auto& y) {
            return x.start < y.start;
        });
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};

/**
 * Definition of Interval:
 * class Interval {
 *   constructor(start, end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

class Solution {
    /**
     * @param {Interval[]} intervals
     * @returns {boolean}
     */
    canAttendMeetings(intervals) {
        intervals.sort((a, b) => a.start - b.start);
        for (let i = 1; i < intervals.length; i++) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
}

/**
 * Definition of Interval:
 * public class Interval {
 *     public int start, end;
 *     public Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    public bool CanAttendMeetings(List<Interval> intervals) {
        intervals.Sort((i1, i2) => i1.start.CompareTo(i2.start));

        for (int i = 1; i < intervals.Count; i++) {
            Interval i1 = intervals[i - 1];
            Interval i2 = intervals[i];

            if (i1.end > i2.start) {
                return false;
            }
        }

        return true;
    }
}

/**
* Definition of Interval:
* type Interval struct {
*    start int
*    end   int
* }
*/

func canAttendMeetings(intervals []Interval) bool {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].start < intervals[j].start
    })

    for i := 1; i < len(intervals); i++ {
        if intervals[i-1].end > intervals[i].start {
            return false
        }
    }
    return true
}

/**
 * Definition of Interval:
 * class Interval(var start: Int, var end: Int) {}
 */

class Solution {
    fun canAttendMeetings(intervals: List<Interval>): Boolean {
        intervals.sortedBy { it.start }.let {
            for (i in 1 until it.size) {
                if (it[i - 1].end > it[i].start) {
                    return false
                }
            }
        }
        return true
    }
}

/**
 * Definition of Interval:
 * class Interval {
 *     var start: Int
 *     var end: Int
 *     init(start: Int, end: Int) {
 *         self.start = start
 *         self.end = end
 *     }
 * }
 */

class Solution {
    func canAttendMeetings(_ intervals: [Interval]) -> Bool {
        let sortedIntervals = intervals.sorted { $0.start < $1.start }
        for i in 1..<sortedIntervals.count {
            if sortedIntervals[i - 1].end > sortedIntervals[i].start {
                return false
            }
        }
        return true
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Using the Wrong Overlap Condition

Meetings overlap when prev.end > curr.start, not prev.end >= curr.start. If one meeting ends exactly when another starts, they do not overlap and can both be attended.

Forgetting to Sort Before Comparing Adjacent Meetings

The sorting approach only works when meetings are sorted by start time. Comparing adjacent meetings in an unsorted list will miss overlaps between non-adjacent intervals.