meeting-rooms

Difficulty: Easy · Topic: Intervals · Practice it on parikshan: /practice/meeting-rooms/start

The story

The calendar engineering team at Google is shipping a feature for Google Workspace: when a user drags a new meeting onto a busy day, the UI should immediately tell them whether the proposed slot conflicts with any existing event. The check has to run in the autocomplete loop, so it has milliseconds at most. The mathematical question reduces to one primitive: given a list of [start, end) intervals on the user's calendar, do any two of them overlap?

That primitive is the smallest possible building block in the intervals cluster. Master it and you can stack it into every richer interval problem: meeting-rooms-ii, Outlook conflict detection, PagerDuty handoff overlap, hotel reservation collision, AWS Lambda concurrency reporting. Master the primitive, then graduate.

What's actually being asked

You are given n meetings, each as a half-open interval [s_i, e_i): start inclusive, end exclusive. One person wants to attend every meeting. Return true if no two of them overlap, otherwise false.

Two meetings that touch (one ends at 3, the next starts at 3) do not count as overlapping; the person finishes the first and walks straight into the second. Half-open semantics is the whole point of the [s, e) notation.

Examples:

[[0,30), [5,10), [15,20)] → false. [0,30) overlaps both others.
[[7,10), [2,4)] → true. After sorting by start: [2,4) and [7,10) are disjoint.
[] → true. A person with no meetings vacuously attends all of them.
[[1,3), [3,5)] → true. Touching is fine, the person walks straight in.
[[5,10)] → true. One meeting cannot conflict with itself.

The naive approach

Compare every pair.

def can_attend_naive(intervals):
    n = len(intervals)
    for i in range(n):
        for j in range(i + 1, n):
            a, b = intervals[i], intervals[j]
            if a[0] < b[1] and b[0] < a[1]:
                return False
    return True

Correct, O(n^2). For n = 10 that is 100 comparisons, fine. For n = 10^5 that is 10^{10} comparisons, many minutes, far over budget. There is a much faster algorithm using the same trick as merge-intervals.

The key insight

If the meetings are sorted by start time, a conflict can only arise between adjacent meetings in sorted order. Why? Suppose A, M, B are three meetings in sorted order with A.start ≤ M.start ≤ B.start. If A and B overlap (so B.start < A.end), then M.start ≤ B.start < A.end, which means M already overlaps A. Neighbours catch every clash. So a single linear sweep of adjacent pairs is enough.

The algorithm is one sentence: sort by start, then check whether each meeting's start is strictly before the previous meeting's end.

The four implementation questions:

Sort by what? By start time.
Sweep what state? Just remember the previous meeting's end.
Compare with which operator? Strict <, because touching is allowed (prev.end == cur.start is not a conflict).
What to return on empty input? true, by convention: a vacuous all-quantifier.

Step-by-step approach

def can_attend(intervals):
    if not intervals: return True
    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

The whole algorithm is a sort plus a six-line loop. There is no auxiliary structure.

Worked example

intervals = [[0,30), [5,10), [15,20)].

After sort by start (already sorted): same order.

Sweep:

i=1: intervals[1][0] = 5, intervals[0][1] = 30. 5 < 30 → conflict. Return false. ✓

Disjoint case: [[7,10), [2,4)].

After sort: [[2,4), [7,10)].

i=1: intervals[1][0] = 7, intervals[0][1] = 4. 7 < 4 is false → no conflict.

Loop ends. Return true. ✓

Touching case: [[1,3), [3,5)]. After sort: same.

i=1: 3 < 3 is false → no conflict. Return true. ✓

That last test is the entire reason the spec uses half-open intervals: it lets touching meetings be neighbours on the calendar without flagging a conflict.

Complexity

Time: O(n log n) for the sort; the sweep is O(n). Sort dominates.
Space: O(n) to hold the parsed list; in-place sort uses O(log n) auxiliary on TimSort.

For n = 10^5 this is around 1.7 million comparisons plus a 10^5-step sweep, well under one second.

Common pitfalls

Using <= instead of <. Touching is allowed by this spec. With <=, the touching case [[1,3), [3,5)] would falsely return false. Always confirm the touching semantics from the problem statement before picking the operator.
Forgetting to sort. Without sort, you would have to compare every pair. The whole speedup hinges on the sort.
Skipping the empty-input case. Most languages handle the empty sweep gracefully and return true. Make sure your code does too.
Off-by-one in the loop bounds. Start at i = 1, compare against i - 1. Starting at i = 0 indexes out of bounds.
Sorting by end time. That key would work for the related "maximum non-overlapping subset" problem, but not here. Sort by start.
Misreading [s_i, e_i) as [s_i, e_i]. The closed-vs-half-open distinction changes the comparison operator. Read the spec.

Where this shows up in the enterprise

Google Calendar and Microsoft Outlook conflict detection: the inline "this conflicts with X" warning on the create-event UI.
Apple Calendar and Fastmail: identical use case, identical algorithm.
PagerDuty oncall handoff checks: detecting overlapping shifts before publishing a rotation.
Hotel and airline reservations at Booking.com and Expedia: detecting double-booking on the same room or seat at the request level.
AWS Lambda concurrent-execution monitoring: when a customer reports unexpected throttling, the first check is "do any two invocations overlap during the throttle window?"
Uber driver scheduling: detecting whether a driver's claimed shifts have any overlap.
Stripe subscription window validation: ensuring a customer is not on two conflicting plans simultaneously.
Compliance log analysis at financial institutions: confirming that no two audit-relevant events overlap on a controlled resource.

The pattern is universal: any time you have a list of [start, end) ranges and need a yes-or-no "do any two overlap" answer, you want this sweep.

Variants you'll see elsewhere

meeting-rooms-ii: the natural escalation. Instead of yes-or-no, return the minimum number of rooms needed to host all meetings without conflict. Same sort by start, but the sweep now uses a min-heap of end times, or an events-sweep with +1 on start and -1 on end. The maximum running sum is the answer.
merge-intervals: same sort, the sweep merges overlapping intervals into one instead of flagging a conflict. The output is a list, not a boolean.
car-pooling: variant of meeting-rooms-ii where each interval has a passenger count. Same events-sweep with weighted deltas.
employee-free-time: invert merged intervals to get gaps. Build on merge-intervals.
interval-scheduling-maximization: sort by end (different key) and greedily pick non-overlapping intervals.

The natural next problem in this cluster is meeting-rooms-ii. The yes-or-no question generalises to a counting question, and the events-sweep technique is worth knowing because it generalises again to flow problems and to streaming concurrency monitoring at services like AWS Lambda and Cloudflare Workers.

How parikshan turns this into a learning loop

This is the smallest interval problem and the entry point to the cluster. The integrated loop is built to make the sort-then-sweep pattern automatic.

Read this article. The two key sentences are "sort by start" and "check cur.start < prev.end".
Solve in practice mode with the AI chat off. Before writing code, draw the three-interval example on a number line and trace the comparison by hand. The drawing is the entire algorithm.
Submit. The bank's dynamic private tests include the touching case, the empty case, a single meeting, identical meetings (which do conflict), and a 10^5-meeting stress test. Touching is the most common spec-misread; the public test catches it instantly.
AI training: Explain the touching semantics if you are unsure. Each request costs a slice of integrity score, so spend deliberately on what matters.
Move to merge-intervals in exam mode. Same sort, the sweep returns a list instead of a boolean. Then graduate to meeting-rooms-ii in practice mode. The events-sweep is the next reusable pattern.

The dispute flow is rarely needed for interval boolean problems (the verdict is unambiguous), but if you genuinely believe your O(n log n) solution should not TLE on the stress test, dispute it. A human reviewer can recalibrate the limit on the bank's reference.

In the AI-integrated workspace

Interval code is the cluster where AI agents most often pick the wrong operator. The most common failure modes:

Wrong comparison operator. <= versus < is a one-character difference that flips half the test cases. Generated code rarely raises the touching-vs-overlap question; you have to.
Wrong sort key. The agent sorts by end time, or by interval length. Output looks plausible on the public sample and breaks on private tests.
O(n^2) instead of O(n log n). The agent generates the nested loop because it shows up first in training data. Passes on n = 3, times out on n = 10^5.
Missing empty-input check. The agent skips the empty case and accesses intervals[0] blindly. Crashes on the trivial test.

The 2027 engineer's discipline for meeting-rooms:

State the sort key and the comparison operator in English before the agent codes. "Sort ascending by start. Return false if any cur.start < prev.end. Strict less-than, because touching is allowed."
Tell the agent to implement the sweep iteratively with an empty-input guard at the top.
Verify on the three-interval example by hand. Always. Cross-check the touching case explicitly.
Stress on edge cases. Empty input, single meeting, identical meetings, touching meetings, reverse-sorted meetings.

Engineers who can name "this is a meeting-rooms sweep" within five seconds of reading a calendar-conflict spec are the ones who direct AI agents productively. Engineers who cannot recognise the pattern review 50 lines of generated nested loops and approve them because they pass the sample. parikshan's loop is built to train the first kind of engineer, and meeting-rooms is the first rung on that ladder.