Attend Maximum Parties

Moderate
0/80
profile
Contributed by
8 upvotes
Asked in companies
AmazonFacebookTwitter

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 :
2
5
1 1
2 2 
1 3
4 4
3 3
2
100 200
300 400
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 :
2
3
1 3
1 3
1 3
4
1 3
1 3
1 3
1 3
Sample Output 2 :
3
3
Hint

Sort the parties by their start dates, how does this help?

Approaches (1)
Priority Queue

Sort the parties by their start date, this will help us keep the track of the parties that are currently running on some particular day.

 

We can store all the parties currently running in a min-priority queue (min-heap), this data structure helps us find and also delete the smallest element in logarithmic time. For some particular day, we can then select a party that has the lowest value of ending date (note that: we only need to store the ending dates of the party in the priority queue), for each such day where we are able to attend a party we will delete the ending date corresponding to the attended party from the priority queue (to avoid double-counting) and also increment the value of the count of parties we have already attended.

 

To implement the above logic, we will iterate over each day, insert all the parties that begin on that particular day into our priority queue, we will then check if the priority queue is non-empty and attend the party ending first, we will delete the entry corresponding to this party from out priority queue and also increment the value of our answer. An important thing we need to check before doing all this is to delete the party from our min-heap that have already ended to avoid them from including in our answer.

 

The steps are as follows :

  1. Sort all the parties according to their starting date.
  2. Initialize a min-heap ‘pq’, to store all the parties that are currently running on some particular day.
  3. Initialize a variable ‘count’ equal to 0, this variable stores the count of parties attended so far.
  4. Initialize a variable ‘idx’ equal to 0, this variable will help to keep the parties and iterate them.
  5. Run a for loop for the variable ‘curD’ from 0 to 5000, the variable ‘curD’ denotes the value of the current day. Inside the loop:
    • From the min-heap, remove all the entries corresponding to the parties that have already ended before the curD’th day.
    • Insert all the parties that start on the curD’th day, use the variable ‘idx’ to traverse the matrix ‘Party’.
    • Check if the size of the min-heap is greater than 0, this means that currently there is at least one party running. Increment the value of ‘count’ and also remove the smallest element from the ‘pq’ as this element corresponds to the party we have just attended.
  6. Finally, return the string ‘count’ as it stores the count of the maximum parties can attend.
Time Complexity

O( D + ( N * log ( N ) ) ), where N denotes the number of parties and D denotes the number of days under consideration.
 

For each day we check if it’s possible to attend a party, according to the constraints mentioned in the question, the entry in the matrix ‘Party’ can’t exceed the value of 5000, therefore we have to consider at max 5000 days.
 

Also in the worst case, each party may be inserted into the priority exactly once, the cost of inserting each entry takes logarithmic time, and this in total take ~N*logN computations.

Hence the time complexity is O( D + N*log(N) ).

Space Complexity

O( N ), where N denotes the number of parties.
 

Extra space is used to store the information about the ending date of parties. In the worst case, the size of our min-heap can grow of the order ~N, this happens when there is a lot of intersection between dates and as a result, there are ~N parties in our min-heap.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Attend Maximum Parties
Full screen
Console