Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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.

```
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

```
1 ≤ T ≤ 10
1 ≤ N ≤ 5000
1 ≤ Party[i][0] ≤ Party[i][1] ≤ 5000
Time limit: 1 sec
```

```
2
5
1 1
2 2
1 3
4 4
3 3
2
100 200
300 400
```

```
4
2
```

```
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.
```

```
2
3
1 3
1 3
1 3
4
1 3
1 3
1 3
1 3
```

```
3
3
```