JanuszTheBusinessman | Topcoder Archive

Problem Statement

Janusz owns a hotel. He has already received some reservations for the upcoming year. The days in the year are numbered 1 through 365. For each valid i, there is a guest who will arrive on day arrivals[i] and depart on day departures[i].

Janusz can give some guests a special promotion. Any guest that gets the special promotion will leave a good review. Additionally, all guests that meet a guest with promotion will also leave a good review. (Here we assume that two guests meet if and only if they are in the hotel on the same day, including the situation when one of them departs on the same day the other one arrives.)

Janusz wants to make sure that all his guests leave good reviews. You are given the int[]s arrivals and departures. Return the smallest possible number of special promotions sufficient to make sure that all guests leave good reviews.

Definition

Class:: JanuszTheBusinessman
Method:: makeGuestsReturn
Parameters:: int[], int[]
Returns:: int
Method signature:: int makeGuestsReturn(int[] arrivals, int[] departures)
(be sure your method is public)

Constraints

arrivals and departures will have the same number of elements.
arrivals will have between 2 and 50 elements, inclusive.
Each element of arrivals and departures will be between 1 and 365, inclusive.
For each valid i arrivals[i] will be less than departures[i].

Examples

```
{2, 10, 6}	
```
```
{6, 11, 9}
```
```
Returns: 2
```
One promotion is not enough. One optimal solution is to give promotions to the guest who arrives on day 2 and to the guest who arrives on day 10. The third guest will meet the first guest on day 6.
```
{2, 10, 23, 34, 45, 123, 1}
```
```
{25, 12, 40, 50, 48, 187, 365}
```
```
Returns: 1
```
One guest is going to stay for the whole season so Janusz can give the promotion only to him.

{8, 12, 20, 30, 54, 54, 68, 75}

{13, 31, 30, 53, 55, 70, 80, 76}

Returns: 3

{124, 328, 135, 234, 347, 124, 39, 99, 116, 148}

{237, 335, 146, 246, 353, 213, 197, 215, 334, 223}

Returns: 2

{154, 1, 340, 111, 92, 237, 170, 113, 241, 91, 228, 134, 191, 86, 59, 115, 277, 328, 12, 6}

{159, 4, 341, 118, 101, 244, 177, 123, 244, 96, 231, 136, 193, 95, 64, 118, 282, 330, 17, 13}

Returns: 14

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.