N meetings in one room
MediumAlways take the meeting that ends soonest
Problem
Given start[] and end[] of meetings, find the maximum number of meetings that can be held in one room without overlap.
Always take the meeting that ends earliest — it leaves the most room for the rest.
The idea
Sorting by finish time and taking every meeting that starts after the last one accepted maximises the count, because finishing earlier leaves the most room for everything after it. This is the classic activity-selection proof.
The trick
- Sort by end time, not start time — sorting by start is wrong.
- Accept when start > lastEnd (or >=, depending on whether touching counts).
- O(n log n).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — start=[1,3,0,5,8,5], end=[2,4,6,7,9,9] Values: 1, 3, 0, 5, 8, 5.
1sort meetings by end time2lastEnd=-inf; count=03for m in meetings:4 if m.start>lastEnd: count++; lastEnd=m.end5return countInput
- array
- [1, 3, 0, 5, 8, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- start = [1,3,0,5,8,5], end = [2,4,6,7,9,9]
- Output:
- 4
- Explanation:
- Pick meetings that finish earliest → 4 fit.
Example 2
- Input:
- start = [1,3], end = [2,4]
- Output:
- 2
- Explanation:
- Both fit → 2.
Example 3
- Input:
- start = [1,2], end = [9,3]
- Output:
- 1
- Explanation:
- The short one leaves room for... just 1 more.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.