TopCoder problem "CommercialPlanner" used in SRM 374 (Division I Level Three)



Problem Statement

    

Our company just released a new product last week. However, only a few people have bought it so far. A study by our sales department reveals that the reason for this is that many people do not know about the new product's existence. The solution is to put a commercial on TV so people hear about the new product.



The TV company schedules the commercials the same way every day, where the k-th commercial starts at starts[k] seconds since the beginning of the day and has a duration of durations[k] seconds. Two commercials cannot overlap in time. A commercial might start on one day and end on the next day.



People can't remember all the commercials they've ever seen. At any given time, a person only remembers the last n commercials he has seen. A person remembers a commercial as soon as it starts, so a partially seen commercial counts as being remembered. The longer a commercial is remembered, the more effective it will be in influencing product decisions.



You are given int[]s starts and durations, the i-th elements of which represent the starting time and duration (both in seconds), respectively, of the i-th existing commercial. Note that these commercials are not given in any particular order. There are secondsPerDay seconds in a day. Our commercial is ourDuration seconds long. You must schedule the commercial so that the time it is remembered for is maximized. It must not overlap with any of the existing commercials. If there are multiple ways to do this, choose the one among them that starts earliest in the day. Return the starting time in seconds since the beginning of the day, or -1 if it is impossible to schedule the commercial.



 

Definition

    
Class:CommercialPlanner
Method:bestMinute
Parameters:int[], int[], int, int, int
Returns:int
Method signature:int bestMinute(int[] starts, int[] durations, int ourDuration, int secondsPerDay, int n)
(be sure your method is public)
    
 

Constraints

-starts will contain between 0 and 50 elements, inclusive.
-Each element of starts will be between 0 and secondsPerDay-1, inclusive.
-durations will contain the same number of elements as starts.
-Each element of durations will be between 1 and secondsPerDay, inclusive.
-ourDuration will be between 1 and secondsPerDay, inclusive.
-secondsPerDay will be between 1 and 2000000000, inclusive.
-n will be between 1 and 50, inclusive.
-For every i and j such that i != j, the i-th commercial will not overlap with the j-th commercial.
 

Examples

0)
    
{30, 5, 17, 45}
{12, 6, 3, 4}
6
50
5
Returns: 11
All the commercials will be remembered every second regardless of where we put ours. The earliest available slot is after the first existing commercial.
1)
    
{30, 5, 17}
{12, 6, 3}
63
100
4
Returns: 42
There is only one position at which our commercial can be scheduled (after the last commercial). Notice that our commercial will be split between two adjacent days.
2)
    
{30, 5, 51, 17, 49}
{12, 6, 10, 3, 1}
1
60
2
Returns: 20
Our commercial will be remembered for 29 seconds.
3)
    
{30, 5, 51, 17, 49}
{12, 6, 10, 3, 1}
64
100
4
Returns: -1
There is no slot with enough space to schedule our commercial.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8284

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10793&pm=8284

Writer:

jbernadas

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev

Problem categories:

Search