You are given n activities with their start and finish times. Write a program to 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.
Problem Note
- Each Activity "i" has start time start[i] and a finish time finish[i], where start[i] ≤ finish[i].
- If any activity selected, activity "i" takes place during the half-open time interval (start[i], finish[i]).
- We assume that, in the input, activities are sorted in increasing order of their finish time.
- Activities i and j are compatible if the intervals [start[i], finish[i]) and [start[j], finish[j]) do not overlap i.e. i and j are compatible if : start[i] ≥ finish[j] or start[j] ≥ finish[i]
Example 1
Input: Consider the following 6 activities which are sorted by finish time
start[] = [1, 3, 0, 5, 8, 5]
finish[] = [2, 4, 6, 7, 9, 9]
Output: [0, 1, 3, 4]
Explanation: A person can perform at most four activities. The maximum set of activities that can be executed by a single person is [0, 1, 3, 4].(These are indexes in start[] and finish[])
Example 2
Input: Consider the following 3 activities which are sorted by finish time.
start[] = [10, 12, 20]
finish[] = [20, 25, 30]
Output: [0, 2]
Explanation: A person can perform at most two activities. The maximum set of activities that can be executed is [0, 2]. (These are indexes in start[] and finish[])