Activity selection / N meetings in one room / maximum trains

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}