Funcia
Lv.1greedysorting

Maximum Meetings

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

meetingsresult
[[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

  • 1≤1 \le meetings.length ≤200,000\le 200{,}000
  • meetings[i] = [start, end], 0≤0 \le start << end ≤109\le 10^9
  • The same request may appear more than once.

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

meetingsExpected
[[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 O(Nlog⁡N)O(N \log N). A DP that looks back over all earlier meetings is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)258 msestimated
C++ (GCC, gnu++23)258 msderived
Python 3.131000 msderived
Java 251770 msderived
Kotlin 2.4 (JVM)1516 msestimated
C# 14 (.NET 10)1516 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.