Last Updated: 22 Apr, 2021
Ninja Sessions
Easy
Asked in company
Ninja has enrolled in ‘N’ practice sessions but he forgot that the timings of some of these sessions can clash with each other. The practice sessions may or may not have the same duration. Ninja is not allowed to leave any session midway. You are given the starting and ending times of each session.
Your task is to determine the maximum number of sessions Ninja can attend without leaving any session midway.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a single integer, ‘N’, denoting the total number of sessions. Then ‘N’ lines follow.
Each of these ‘N’ lines contains two space-separated integers, denoting the starting time and ending time of the ‘ith’ session.
Output Format:
For each test case, print a single integer, denoting the maximum number of sessions Ninja can attend.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= A,B, <= 10^9
Time Limit: 1sec
Approaches
The approach is to observe that to maximize the total number of sessions that Ninja can attend, it is always beneficial to attend the session that ends the earliest. So, we can sort all the sessions according to the non-decreasing order of their ending time. We can define a variable to keep track of the time at which the session which Ninja is currently attending ends. Now, we can loop through all the sessions and if a session starts at a time later than the time at which the current session ends, then Ninja will be able to attend this session and we increase the value of our final answer by 1.
Steps:
- Initialize a variable, say sessionsAttended=0, to store the maximum possible number of sessions that Ninja can attend. This will be our final answer.
- Initialize a variable, say currSessionEnds=0, to keep track of the time at which the session which Ninja is currently attending ends.
- Now, we sort the sessions according to the non-decreasing order of their ending time. This means that we will sort according to index 1 of each vector since the ending time is present at this index. We can use a lambda function to achieve this.
- Run a loop from i=0 to i<sessions.size(), and do:
- Define a variable, say startTime, and make it equal to sessions[i][0]. This is the starting time of the ‘ith’ session.
- Define a variable, say endTime, and make it equal to sessions[i][1]. This is the ending time of the ‘ith’ session.
- If the current session starts at a time later than when the current session ends, then Ninja will be able to attend this session and increase the value of our final answer by 1. Formally, if startTime >= currSessionEnds, do:
- Increase the value of sessionsAttended by 1 because Ninja can attend this session.
- Make currSessionEnds = endTime. This is because Ninja is attending the ‘ith’ session and this session ends at endTime.
- Finally, we return the value of sessionsAttended.