Meeting Rooms
Problem Statement
You are given an array intervals where intervals[i] = [start_i, end_i] represents one meeting. Determine whether a single person can attend every meeting.
A meeting that ends at time t frees the person immediately, so another meeting may start at exactly t without overlapping.
Input
An array intervals of meeting time ranges, where each range is [start_i, end_i].
Output
A boolean: true if no two meetings overlap, otherwise false.
Constraints
- •
0 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
0 <= start_i < end_i <= 10^6
Examples
Example 1
intervals = [[0,30],[5,10],[15,20]]
falseExample 2
intervals = [[7,10],[2,4]]
trueExample 3
intervals = [[1,5],[5,8]]
trueLearning Objectives
- Recognise when chronological sorting turns interval overlap checks into adjacent comparisons.
- Explain why sorting by start time is the correct greedy ordering for feasibility.
- Handle the boundary case where one meeting ends exactly when another starts.
- Separate interval feasibility from interval selection problems that optimise a count.
Intuition
Greedy Insight: Put the meetings in the order the person would experience them: increasing start time. Once meetings are sorted this way, any conflict must appear between a meeting and the meeting immediately before it in the sorted order.
The useful tracked value is the previous meeting end time. If the current start is before that end, the current meeting begins while the previous one is still running, so attendance is impossible. If every current start is at least the previous end, the person can walk through the whole calendar.
The wrong sort key trap is to sort by duration, by original input order, or by end time because those orders do not represent the actual chronological sequence of commitments. Earliest end is powerful when choosing the maximum number of compatible intervals, but for simply verifying one calendar, start time is the natural order.
Common mistakes
- ×Checking only the input order and missing overlaps after a later interval starts earlier.
- ×Treating **start == previousEnd** as an overlap even though back-to-back meetings are allowed.
- ×Sorting by interval length, which has no relationship to calendar feasibility.
- ×Comparing the current meeting against every previous meeting instead of using the sorted adjacent property.
Algorithm Explanation
Greedy strategy Sort meetings by increasing start time and scan once, comparing each meeting with the meeting that starts immediately before it.
Why it works After sorting by start time, every future meeting starts no earlier than the current meeting. If the current meeting does not overlap the immediately previous one, then it cannot overlap any earlier meeting whose end has already been verified to finish before the previous start chain.
Proof of correctness Consider the meetings in sorted start-time order. If the algorithm finds a pair where currentStart < previousEnd, those two real meetings overlap in time, so no valid single-person schedule exists.
Now suppose the algorithm finishes without finding such a pair. For any earlier meeting i and later meeting j, the consecutive checks give end_i <= start_{i + 1}, and sorted starts give start_{i + 1} <= start_j. Therefore end_i <= start_j, so meeting i cannot overlap meeting j. Every pair is non-overlapping, so the person can attend all meetings.
This is an exchange argument in miniature: any valid calendar can be rewritten in chronological start order without changing the meetings. The greedy order is therefore safe because it is just the only order in which one person could actually attend them.
Algorithm
- Sort intervals by start time.
- Walk from the second meeting to the end.
- If intervals[i][0] < intervals[i - 1][1], return false.
- If the scan completes, return true.
Solutions
Solution: Sort by start time
Sorting creates the chronological order of the calendar. In that order, any overlap must be visible between neighbouring intervals, so one linear scan is enough.
Step-by-step
- Sort all meetings by their start time.
- Start at index 1 because the first meeting has no previous meeting to conflict with.
- Compare the current start with the previous end.
- Return false immediately on an overlap; otherwise return true after all comparisons pass.
O(n log n)
O(1)
Sorting dominates the runtime; the scan is linear. Java may use stack space internally for sorting.
Java implementation
Dry Run
Sample input
intervals = [[0,30],[5,10],[15,20]]. After sorting by start time, the order is unchanged.
| current meeting | previous end | current start | overlap? | decision |
|---|---|---|---|---|
| [0,30] | none | 0 | no | set previous end to 30 |
| [5,10] | 30 | 5 | yes | return false |
The scan stops as soon as 5 < 30. The second meeting starts while the first is still running, so a single person cannot attend every meeting.
Interview Tips
Lead with the invariant: after sorting by start time, all meetings already checked form a non-overlapping prefix. Then the next meeting only needs to be compared with the previous meeting in that prefix. Also call out the equality case; many interviewers include back-to-back meetings to test boundary handling.
Likely follow-ups
- How would you return the first conflicting pair instead of a boolean?
- How would the answer change if a cleanup buffer of **k** minutes were required between meetings?
- What if you receive meetings as a stream rather than all at once?
- How would you solve the version that asks for the minimum number of rooms?
Similar Problems
Key Takeaways
- For one-person calendar feasibility, sort intervals by start time.
- After chronological sorting, only adjacent meetings need to be compared.
- A meeting starting exactly at the previous end is not an overlap.
- Do not confuse feasibility checking with maximum compatible interval selection.