CommercialPlanner
SRM 374 · 2007-11-06 · by jbernadas
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
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.
{}
{}
3600
3600
1
Returns: 0
We can take all the day for our commercial.
{30, 5, 17, 45}
{12, 6, 3, 4}
4
50
5
Returns: 0
Regardless of where we put our commercial, all commercials will be remembered every second of the day, so we put it at the beginning of the day.
{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.
{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.
{30, 5, 17}
{12, 6, 3}
64
100
4
Returns: -1
There is no slot with enough space to schedule our commercial.
{30, 5, 51, 17, 49}
{12, 6, 10, 3, 1}
1
60
2
Returns: 20
Our commercial will be remembered for 29 seconds.
{30, 5, 51, 17, 49}
{12, 6, 10, 3, 1}
1
100
2
Returns: 61
Our commercial will be remembered for 56 seconds. It will be remembered from the 61-th second in a day until the 17-th second of the next day.
{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.
{0, 40000000, 80000000, 120000000, 160000000,
200000000, 240000000, 280000000, 320000000,
360000000, 400000000, 440000000, 480000000,
520000000, 560000000, 600000000, 640000000,
680000000, 720000000, 760000000, 800000000,
840000000, 880000000, 920000000, 960000000,
1000000000, 1040000000, 1080000000, 1120000000,
1160000000, 1200000000, 1240000000, 1280000000,
1320000000, 1360000000, 1400000000, 1440000000,
1480000000, 1520000000, 1560000000, 1600000000,
1640000000, 1680000000, 1720000000, 1760000000,
1800000000, 1840000000, 1880000000, 1920000000,
1960000000}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
1
2000000000
50
Returns: 1
Watch out for time limits.
Submissions are judged against all 227 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CommercialPlanner with a public method int bestMinute(vector<int> starts, vector<int> durations, int ourDuration, int secondsPerDay, int n) · 227 test cases · 2 s / 256 MB per case