Activity selection / N meetings in one room / maximum trains
Problem
Given activities (or meetings) with start and end times, select as many as possible that do not overlap, for a single person or room. Maximum Trains applies the same idea separately to each platform.
Example 1
Input: start = [1, 3, 0, 5, 8, 5], end = [2, 4, 6, 7, 9, 9] Output: 4
Meetings 1, 2, 4, 5 (by 1-based index).
Also asked as: Activity Selection Problem · Find maximum meetings in one room · Maximum trains for which stoppage can be provided
Test cases
Case 1
Input: [[1,2],[3,4],[0,6],[5,7],[8,9],[5,9]] Expected: 4
Case 2
Input: [[1,3],[2,5],[4,6]] Expected: 2
Case 3
Input: [[1,2]] Expected: 1
Case 4
Input: [] Expected: 0
View solutionHide solution1 approach
1. Sort by finish time, greedily take non-overlapping
Time O(n log n)Space O(1)
Always pick the activity that finishes earliest and does not clash with the last chosen one — it leaves the most room for the rest.
function maxActivities(activities) { // [start, end] activities.sort((a, b) => a[1] - b[1]); let count = 0, lastEnd = -Infinity; for (const [s, e] of activities) { if (s >= lastEnd) { count++; lastEnd = e; } } return count;}