Clash-Free Calendar
EasyIntervalsFree
Problem
A consultant exports her calendar as a list of meetings, where meetings[i] = [start, end] describes a meeting that occupies the half-open time range [start, end): it begins at start and is over by end.
Return true if she can attend every meeting in person, that is, no two meetings overlap. A meeting that ends at t and another that starts at t do not overlap.
Example 1
- Input:
- meetings = [[0, 30], [5, 10], [15, 20]]
- Output:
- false
[5, 10) lies inside [0, 30), so two meetings run at the same time.
Example 2
- Input:
- meetings = [[7, 10], [2, 4]]
- Output:
- true
Sorted by start: [2, 4) ends before [7, 10) begins.
Example 3
- Input:
- meetings = [[1, 5], [5, 8]]
- Output:
- true
The first meeting is over exactly when the second starts.
Constraints
- 0 ≤ meetings.length ≤ 10^4
- 0 ≤ start < end ≤ 10^6
Hint
Show the first hint
Overlaps are hard to spot in arbitrary order. What order would put potentially clashing meetings next to each other?
Walkthrough
How to approach it
01Clarify before coding
- Are the ranges closed or half-open? Half-open: [1, 5) and [5, 8) touch but do not overlap.
- Can the list be empty? Yes, and an empty calendar is trivially clash-free.
- Is the input sorted? No, meetings come in any order.
02Brute force
Compare every pair of meetings and report a clash when max(start) < min(end).
Cost: O(n²) time, O(1) space: 50 million pair checks for n = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.