Last Updated: 3 Jan, 2021
Maximum activities
Easy
Asked in companies
You are given N activities with their start time Start[] and finish time Finish[]. You need to tell the maximum number of activities a single person can perform.
Note:
A person can only work on a single activity at a time. The start time of one activity can coincide with the end time of another.
Input format:
The first line contains an integer 'T' denoting the number of test cases or queries to be run.
The first line of each test case or query contains a single integers 'N' denoting the number of activities.
The second line of each test case contains N single space-separated integers denoting the starting time of N activities respectively.
The third line of each test case contains N single space-separated integers denoting the finishing time of N activities respectively.
Output Format:
For each test case, print the maximum number of activities a single person can perform.
Constraints:
1 <= T <= 5
1 <= N <= (10^5)
0 <= Start[i] < Finish[i] <= (10^9)
Time Limit: 1 sec
Approaches
- The idea is to create an array of pair ACTIVITY of size N. where the first element of pair is finish time and the second element is the start time of activity.
- Sort the ACTIVITY array in increasing order of finish time.
- Select the first activity of the sorted ACTIVITY as your first activity and increase your count of the number of activities performed, say maxActivity, also maintain one variable currentTime to maintain the current finish time. Initialize currentTime with a finish time of first activity picked.
- Now iterate through the rest, ACTIVITY array from left to right and for each ACTIVITY[i], check if it is possible to perform that activity or not. If the start time of the ACTIVITY[i] is greater than or equal to the currentTime, it means it is possible to perform ACTIVITY[i], increment your maxActivity count and update currentTime with a finish time of ACTIVITY[i].
- Return maxActivity.