Attend Maximum Parties

Moderate

0/80

Contributed by

8 upvotes

Asked in companies

Problem statement

There are ‘N’ parties organised and you are also given a matrix ‘Party’ where Party[i] contains two integers the starting date and the ending date (both inclusive) of the i’th party.

You are only allowed to attend a single party each day, you are a party animal and want to attend a maximum number of different parties, find the maximum parties that you can attend.

Example :

If ‘N’ = 5 and ‘Party’ = { {1, 1}, {2, 2}, {1, 3}, {4, 4}, {3, 3}, }

You can attend a maximum of 4 different parties, you can attend the 1’st party on the 1’st day, 2’nd party on the 2’nd day, 3’rd party on the 3’rd day and 4’th party on the 4’th day. But it is impossible to attend the 5’th (last) party, as if we were to attend this party then we would have to attend it instead of the 3’rd party (3’rd day), there may be many other combinations possible, but no combination will result in a maximum number of different parties attend greater than four.

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

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the total number of parties organized.

The next N lines each contain two integers ‘Party[i][0]’ and ‘Party[i][1]’, denoting the starting and ending day of the i’th party.

Output Format :

For each test case, print the count of the maximum different parties you can attend.

Output for each test case will be printed in a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10      
1 ≤ N ≤ 5000
1 ≤ Party[i][0] ≤ Party[i][1] ≤ 5000

Time limit: 1 sec

Sample Input 1 :

Sample Output 1 :

4
2

Explanation For Sample Input 1 :

For test case 1 :
We will print 4 because:
We can attend a maximum of 4 different parties, you can attend the 1’st party on the 1’st day, 2’nd party on the 2’nd day, 3’rd party on the 3’rd day and 4’th party on the 4’th day. But it is impossible to attend the 5’th (last) party, as if we were to attend this party then we would have to attend it instead of the 3’nd party (3’rd day), there may be many other combinations possible, but no combination will result in a maximum number of different parties attend greater than four.

For test case 2 : 
We will print 2 because: 
We can attend both the parties, we may attend the 1’th party on the 100’th day and the 2’nd party on the 300’th day.

Sample Input 2 :

Sample Output 2 :

3
3

Console