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