Skip to main content
Back to ChallengesActivity Selection ProblemMedium 25 min

Activity Selection Problem

Given N activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Examples

Input: start = [10, 12, 20], finish = [20, 25, 30]
Output: 2
A person can perform at most two activities: [10, 20] and [20, 30].

Constraints

  • • 1 <= start.length <= 10^5
  • • 0 <= start[i] <= finish[i] <= 10^5

Complexity Analysis

Time
O(N log N)
dominated by sorting.
Space
O(N)
creating an array of objects.

Test Cases

#1 Overlap handled
Input: start = [10,12,20], finish = [20,25,30]
Expected: 2
#2 Standard case
Input: start = [1,3,0,5,8,5], finish = [2,4,6,7,9,9]
Expected: 4
Output
Click "Run Code" to see output here...