DSAPrep
EasyIntervals

Meeting Rooms

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings.

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Explanation: [0,30] overlaps both [5,10] and [15,20], so one person cannot attend all three.

Example 2

Input: intervals = [[7,10],[2,4]]
Output: true
Explanation: [2,4] ends before [7,10] starts, so there is no overlap.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i < end_i <= 10^6
View original on LeetCode ↗

Brute Force (Compare Every Pair)

Time O(n²)Space O(1)

A person can attend every meeting only if no two meetings overlap. Check every pair directly: two intervals [s1, e1] and [s2, e2] overlap when s1 < e2 and s2 < e1.

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)
        for i in range(n):
            s1, e1 = intervals[i]
            for j in range(i + 1, n):
                s2, e2 = intervals[j]
                if s1 < e2 and s2 < e1:
                    return False
        return True

Correct but wasteful: checking all O(n²) pairs ignores that sorting the meetings by start time turns “any overlap” into an adjacent-pair check.

Sort by Start, Check Neighbors

OptimalTime O(n log n)Space O(1)

Sort meetings by start time. After sorting, if any meeting overlaps another, it must overlap the meeting immediately before it (its start is the smallest among all later meetings, so it is the first one that could possibly still be inside the previous meeting’s window). So a single pass comparing each meeting to its predecessor is enough.

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort(key=lambda iv: iv[0])
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True

Tracing intervals = [[0,30],[5,10],[15,20]] (already sorted by start):

Sorted intervals

[0, 30]
[5, 10]
[15, 20]
1 / 2
merging

Sorted by start. [0,30] is the first meeting; nothing to compare yet.

Contrast with intervals = [[7,10],[2,4]], sorted to [[2,4],[7,10]]:

Sorted intervals

[2, 4]
[7, 10]
1 / 2
merging

Sorted by start. [2,4] is the first meeting; nothing to compare yet.

Complexity: dominated by the sort → O(n log n) time; the scan uses no extra data structures → O(1) extra space.