Meeting Rooms

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 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

Watch how a single sorted pass compares each meeting only with its predecessor:

The first overlap ends the scan. Contrast with intervals = [[7,10],[2,4]], sorted to [[2,4],[7,10]]: the only neighbor check is 7 < 4, which is false, so the loop finishes and the answer is true.

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