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[])``````