Ninja Sessions

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in company
Flipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
2
1 4
6 7
Sample Output 1:
2
Explanation For Sample Input 1:
In the given test case, Ninja can attend both the sessions he enrolled in. He can attend the first session, which starts at 1 and ends at 4. He can also attend the second session because this session starts at 6. So, our final answer will be 2.
Sample Input 2:
1
3
1 4
2 5
4 7
Sample Output 2:
2
Hint

Sort all the sessions according to the non-decreasing order of their ending time.

Approaches (1)
Using Sorting

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.
Time Complexity

O(N * log N), where ‘N’ is the total number of sessions Ninja enrolled in.

 

We are sorting all the sessions according to their ending times. Since there are a total of ‘N’ sessions, this sorting process takes O(N * log N) time. Now, we are traversing through all sessions and comparing their starting times. This takes O(1) time for each session and thus takes O(N) overall. 

 

Hence, our overall complexity becomes O(N * log N).

Space Complexity

O(1)

 

We are not using any extra auxiliary space.

Code Solution
(100% EXP penalty)
Ninja Sessions
Full screen
Console