Here is the problem statement:
You have a light bulb for an interval of N seconds, where N is given.
At the moment 0, the bulb lights up and at the moment N, it goes out.
independently of the switches. From time 1 to time N-1, you have a maximum
of N-2 switches in the form of an array called switches, which turn
the light bulb in contrast to what it is currently ie if it is on
it will go out and vice versa. For example, suppose N = 8 and switches
= [1,2]. The bulb will turn on at time 0, a switch at the time 1 will turn it off, a switch at the time will turn it on and it will remain on.
until 8 o'clock, when it goes out. Therefore, the time it remains is
equal to 1-0 + 8-2 = 7.
Now suppose you need to insert a switch in this interval, where
is not already a present switch. What is the maximum duration of the
The bulb stays on once you have inserted the switch. For example, in the
case above, the solution would be 6 since the insertion of a switch at the moment 7
keep the time as the bulb goes to maximum. Since 1-0 + 7-2 = 6,
the answer is 6.
I've solved the problem using a brute-force solution, using the following reasoning: if you insert a switch at the moment k, the bulb states before this one would not be affected and the states of the bulb from the moment k to the moment N will be reversed, and so you can find the time that it passes after the time k with (N – k) – t, where t is the time that it would pass from time k to N without the inserted switch. Therefore, I can calculate the time that the bulb would spend for each time position of the inserted switch and maximize it. However, since the computation of the time spent by the light bulb is an operation O (n) and I consume all the possible positions, my solution is O (n ^ 2), which has resulted in the same. code expiration for some test cases.
Can someone offer a better solution?