136. Activity Selection Problem

Given n activities with their start and end times, find the maximum number of activities a single person can perform, assuming a person can only work on one activity at a time (an activity that starts exactly when another ends is allowed).

Input: The first line contains an integer n. The second line contains n space-separated start times, and the third line contains n space-separated end times, for each of the n activities. Output: Print a single integer - the maximum number of non-overlapping activities that can be performed.

1 <= n <= 10^5

Sorting by START time or by DURATION instead of END time would NOT give a correct greedy algorithm here - end-time sorting is the one specific choice that makes the 'always pick the earliest-ending compatible option' strategy provably optimal.

Given several activities with start and end times, find the maximum number a single person can attend, one at a time. Brute force: Try every possible subset of non-overlapping activities directly and find the largest one - this is exponential, completely impractical for large n. Optimised: Sorting by END time and always greedily picking the earliest-ending compatible activity is provably optimal: finishing as early as possible always leaves the maximum remaining time for future activities, so this greedy choice never loses to any alternative strategy.

Recursively consider each activity in turn and branch on whether to include it or skip it, only allowing an activity to be included if its start time is not earlier than the end time of the most recently included activity, tracking the maximum count of compatible activities found across all branches. This checks every possible subset of mutually compatible activities and is guaranteed correct, but the number of subsets grows exponentially with the number of activities. Time: O(2^n) Space: O(n)

Sort the activities by end time, then define dp[i] as the maximum number of compatible activities achievable considering only the first i (sorted) activities, where dp[i] = max(dp[i-1], 1 + dp[j]) and j is the largest index whose end time is not after activity i's start time, found via binary search on the sorted end times. This is a more general technique that would also extend to weighted variants of the problem, and it avoids the brute force's exponential subset exploration by building up the answer from smaller prefixes. Time: O(n log n) Space: O(n)

Sort all activities by their end time, then scan through them once, greedily picking every activity whose start time is not earlier than the end time of the last activity picked so far. This works because, among all activities compatible with what's been picked, the one that finishes earliest always leaves the most room for future activities - a classic exchange-argument proof of greedy optimality specific to this unweighted scheduling problem. It reaches the same optimal count as the DP approach but with a single linear pass after sorting and no extra table. Time: O(n log n) Space: O(1) extra

1. Sort all activities by their END time. 2. Greedily pick the first activity (earliest ending). 3. For every subsequent activity, pick it only if its start time is not before the end time of the last picked activity - this always leaves the most room for future activities.

Time: O(n log n), dominated by the sort - the greedy selection pass afterward is O(n). Space: O(1) extra space beyond the sorted array.

n = 1, activities that touch exactly at endpoints (one starting exactly when another ends, which is allowed), and n = 10^5 for performance.

This is THE canonical greedy-algorithm-correctness proof exercise - be ready to explain WHY sorting by end time (not start time, not duration) is what makes the greedy choice provably optimal, typically via an exchange argument.