Maximum Meetings
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
There is one meeting room and a list of requests meetings, where meetings[i] = [start, end] runs from time start to
time end. Only one meeting can be held at a time and a meeting cannot be interrupted, but a meeting may start exactly when
the previous one ends ([1, 3] and [3, 5] are compatible).
Return the maximum number of meetings that can be held.
Examples
| meetings | result |
|---|---|
[[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]] | 4 |
[[1, 2], [2, 3], [3, 4]] | 3 |
[[0, 10], [1, 2], [3, 4]] | 2 |
Example 1 — hold [1, 4], [5, 7], [8, 11] and [12, 16].
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(meetings: int[][]) → int
Constraints
-
meetings.length meetings[i] = [start, end],startend- The same request may appear more than once.
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| meetings | Expected |
|---|---|
[[1,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]] | 4 |
[[1,2],[2,3],[3,4]] | 3 |
[[0,10],[1,2],[3,4]] | 2 |
Hint
Hint
Always take the meeting that ends first: swapping the first meeting of any optimal schedule for it never creates an overlap. Sort by end time and greedily take every meeting that starts no earlier than the last chosen one ends, in . A DP that looks back over all earlier meetings is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 258 ms | estimated |
| C++ (GCC, gnu++23) | 258 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1770 ms | derived |
| Kotlin 2.4 (JVM) | 1516 ms | estimated |
| C# 14 (.NET 10) | 1516 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 3 | verdict only |