Determine Whether One Person Can Attend Every Meeting
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Determine Whether One Person Can Attend Every Meeting
### Problem
Implement `canAttendAllMeetings(intervals) -> canAttend`.
Each meeting is a half-open interval `[start, end)`. Return `true` if no two meetings overlap, and `false` otherwise. Because intervals are half-open, a meeting ending at time `t` does not conflict with another meeting starting at `t`.
### Portable Contract
- `intervals` is a JSON array whose elements are two-integer arrays `[start, end]`.
- `0 <= intervals.length <= 12,000`.
- `0 <= start < end <= 9,000,000,000,000`; all values are exact in signed 64-bit integers and JavaScript integer arithmetic.
- Duplicate intervals are allowed and overlap whenever they are nonempty.
- An empty or one-meeting input returns `true`.
- Do not modify `intervals`.
- Let `B` be the compact UTF-8 JSON byte length of `intervals`, counting every bracket, comma, minus sign, and digit. Inputs satisfy `B <= 160,000`; the serialized Boolean result is at most five bytes.
- Target `O(n log n)` time and `O(n)` auxiliary space, or better, for `n = intervals.length`.
Python and JavaScript receive arrays of integer pairs. Java may use `List<List<Long>>`, and C++ may use `vector<vector<long long>>`; the result is Boolean in every language.
```hint Look only at the nearest potential conflict
After choosing a useful ordering, determine which previously considered meeting is sufficient to test against the next one.
```
```hint Preserve the half-open boundary
Use a comparison that treats an end time equal to the next start time as non-overlapping.
```
### Examples
```text
intervals = [[0, 10], [10, 12], [15, 20]]
canAttend = true
```
```text
intervals = [[7, 12], [2, 8]]
canAttend = false
```
### Discussion Requirements
- Explain why checking only adjacent intervals is sufficient after the chosen ordering.
- Cover touching endpoints, duplicate intervals, and a nested interval.
- State why sorting a copy is necessary when the input must remain unchanged.
Quick Answer: Determine whether one person can attend every meeting in a collection of half-open time intervals. This question checks overlap reasoning, endpoint semantics, duplicate and nested intervals, input immutability, and time-complexity trade-offs.
Given a list of meetings, decide whether one person could attend every one of them
without a scheduling conflict.
Each meeting is a half-open interval `[start, end)`: it occupies every instant `t` with
`start <= t < end`. Two meetings **conflict** when they share at least one instant.
Because the intervals are half-open, a meeting that ends at time `t` does **not** conflict
with a meeting that starts at time `t`.
Implement `canAttendAllMeetings(intervals)`.
- `intervals` is an array whose elements are two-element arrays `[start, end]`.
- Return `true` when no two meetings conflict, and `false` otherwise.
- An empty list and a one-meeting list both return `true`.
- Duplicate meetings are allowed. Every meeting is nonempty (`start < end`), so two
identical meetings always conflict.
- The input may arrive in any order; conflicting meetings are not necessarily adjacent
entries of the given array.
- Do not modify `intervals`. Sort a copy if you want sorted order.
## Output
The answer is a single boolean: `true` if all meetings can be attended, `false` otherwise.
Exactly one boolean is correct for any input, so no ordering or tie-breaking rule applies.
## Examples
**Example 1**
```text
intervals = [[0, 10], [10, 12], [15, 20]]
output = true
```
`[0, 10)` ends at the exact instant `[10, 12)` begins, and half-open intervals that merely
touch do not overlap. `[15, 20)` starts after `[10, 12)` has ended, so one person can attend
all three meetings.
**Example 2**
```text
intervals = [[7, 12], [2, 8]]
output = false
```
The two meetings both occupy every instant in `[7, 8)`, so they conflict and the answer is
`false`. Note that the array is not sorted by start time.
## Integer width
Times run as high as `9,000,000,000,000`, far above the signed 32-bit range
(`2,147,483,647`). Use `long` in Java and `long long` in C++; a 32-bit `int` silently
truncates these times and returns the wrong answer. Every value is exact in a signed 64-bit
integer and in a JavaScript number.
## Signatures
- Python: `canAttendAllMeetings(intervals) -> bool`
- JavaScript: `canAttendAllMeetings(intervals) -> boolean`
- Java: `boolean canAttendAllMeetings(long[][] intervals)`
- C++: `bool canAttendAllMeetings(std::vector<std::vector<long long>>& intervals)`
Constraints
- 0 <= intervals.length <= 12,000
- Each element of intervals is exactly two integers, [start, end]
- 0 <= start < end <= 9,000,000,000,000
- Every start and end is exact in a signed 64-bit integer and in JavaScript integer arithmetic; values exceed the signed 32-bit range, so Java must use long and C++ must use long long
- Duplicate intervals are allowed, and they always overlap because every interval is nonempty
- An empty or one-meeting input returns true
- intervals must not be modified
- Let B be the compact UTF-8 JSON byte length of intervals, counting every bracket, comma, minus sign, and digit; inputs satisfy B <= 160,000, and the serialized boolean result is at most five bytes
- Target O(n log n) time and O(n) auxiliary space, or better, for n = intervals.length
Examples
Input: ([],)
Expected Output: True
Explanation: Empty input: there is no pair of meetings, so the answer is true.
Input: ([[0, 1]],)
Expected Output: True
Explanation: A single meeting can always be attended.
Hints
- Meetings are given in arbitrary order, so the first useful move is to choose an ordering under which a conflict is guaranteed to be visible locally.
- Once the meetings are ordered, work out which single previously seen meeting is enough to test the next one against, and why no earlier meeting can be missed.
- The half-open rule turns on one comparison operator: decide whether an end time equal to the next start time should count as a conflict, then pick < or <= to match.