Maximum activities

Easy

0/40

Average time to solve is 15m

Contributed by

52 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

3
1

Explanation For Sample Input 1:

For test case 1: 
A person can perform maximum of 3 activities, by performing the activities in the given order 1 - > 3 -> 2.

For test case 2:
As the starting of all the activities is the same, a person can perform a maximum of 1 activity.

Sample Input 2:

Sample Output 2:

4 
1

Hint 1

The idea is to perform the activities greedily.

Approaches (1)

Approach 1

Greedy Approach

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.

Time Complexity

O(N * logN), where N is the number of activities.

In the worst case, we are sorting an ACTIVITY array of size N.

Space Complexity

O(N), where N is the number of activities.

In the worst case, we are creating an ACTIVITY array of size N.

(75% EXP penalty)

(100% EXP penalty)

Maximum activities

Console