See the original problem on HackerRank.
Solutions
You might see this problem as one on intervals. Here, the input is sorted and the lenght of each interval is fixed (the duration of the recording). Every interval spans from ts[i]
to ts[i] + duration
(excluded).
The solution to this problem is the cardinality of the set containing all the seconds recorded. For example, consider this input:


First, the app records from 2 to 7 (excluding the latter):


In the meantime, from 4 to 9 (excluding the latter):


Finally, from 10 to 15 (excluding the latter):


If we intersect all such sequences we get:


The cardinality of this set is 12, as expected.
One valid solution consists in simulating the creation of this set. Here is an example by Omar Chehaimi:


The solution passes all the test cases, however it is \(O(N \cdot duration)\) that is expensive when \(duration\) is close to \(N\).
We can do better by counting the number of integers that every trigger (ts[i]
) contributes with.
We have to distinguish two cases:
ts[i]
does not overlap with the previousts[i1]
ts[i]
does overlap with the previousts[i1]
The former is easy: the number of seconds that ts[i]
adds to the counter is just duration
. For example, consider ts[2]
:


Since ts[2]
does not overlap with ts[1]
, it adds 5
brand new integers to the party.
On the other hand, ts[1]
adds only 2
new integers to the party. Indeed, 2
is the just the difference ts[1]  ts[0] = 4  2
. We assume that ts[0]
does not overlap with any preceding triggers, for this reason we initialize the counter to duration
.
To sum it up: the solution is the sum 5 + 2 + 5
, or:


Maybe you are already seeing a pattern here: when ts[i]
overlaps with ts[i1]
then the contribution is ts[i]  ts[i1]
, otherwise it is equal to duration
.
We can turn this idea into code by explicitly checking against the “overlapping condition”:




However, we can do even better. First of all, curr.second  prev.second
can be reduced to ts[i] + duration  1  (ts[i1] + duration  1) = ts[i]  ts[i1]
:


Actually, you can notice that the condition can be rewritten as duration > ts[i]  ts[i1]
and that such a condition is none other than choosing either duration
or ts[i]  ts[i1]
depending on which is the smallest…this leads to:


Intuitively, every ts[i]
can’t contribute more than duration
and at least ts[i]  ts[i1]
seconds.
Playing with patterns
The code above can be written in terms of the wellknown pattern zip  map  reduce. In C++:


C++ ranges make things a bit nicer:


Try it on Compiler Explorer.
And this is an awesome application of pattern with Linq by Silvestro Pomes:


Here is another slick solution in Python by Andrea Battistello:

