JanuszTheBusinessman
SRM 645 · 2014-12-30 · by w10d
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
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].
{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
{1,2,3,4,5,6}
{2,3,4,5,6,7}
Returns: 2
min dominating set != min vertex cover
{1,2,3,4,5,6,7}
{2,3,365,5,6,7,8}
Returns: 2
evima's test
Submissions are judged against all 161 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class JanuszTheBusinessman with a public method int makeGuestsReturn(vector<int> arrivals, vector<int> departures) · 161 test cases · 2 s / 256 MB per case