algorithm - 面试题: Insert switch to maximize time lightbulb spends on

Question

这里是问题陈述:

You have a lightbulb for an interval of N seconds, where N is given. At time 0, the lightbulb switches on, and at time N, it switches off, regardless of any 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 lightbulb to the opposite of what it currently is i.e. if it's on it'll turn off and vice versa. For example suppose N = 8 and switches = [1,2]. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain on until time 8, when it turns off. Hence, the time it remains on is equal to 1-0 + 8-2 = 7.

Now suppose you have to insert a switch in this interval, where there is not already a switch present. What is the maximum time the lightbulb remains on once you insert the switch. For example, in the above case, the solution would be 6 since inserting a switch at time 7 keeps the time the lightbulb spends on maximum. Since 1-0 + 7-2 = 6, the answer is 6.

我使用暴力解决方案解决了这个问题，使用的推理是如果你在时间 k 插入一个开关，在此之前灯泡的状态不会受到影响，并且灯泡从时间 k 到时间的状态N 将被反转，因此您可以通过 (N - k) - t 找到它在时间 k 之后花费的时间，其中 t 是它在没有插入开关的情况下从时间 k 到 N 花费的时间。因此，我可以计算出灯泡在插入开关的每个时间位置所花费的时间并将其最大化。但是，由于计算灯泡点亮的时间是一个 O(n) 操作，并且我遍历了所有可能的位置，所以我的解决方案是 O(n^2)，这导致我的代码在某些测试用例中超时。

有人可以提出更好的解决方案吗？

Answer 1

如果我们在之前打开的 block 中插入，就像在您的示例中一样，我们希望将它插入到尽可能接近 on 时间段的末尾。如果我们要插入之前的 off block ，我们会将其放置在尽可能靠近该周期开始的位置，以最大化该 block 的新 on 时间。

要在 O(1) 中计算任何一个选择的效用，我们可以引用从数组末尾开始累积的交错前缀和。 (正如 Nico Schertler 在上面所评论的那样，我们可以在具有恒定空间的末尾的单个遍历中动态地执行整个计算 - 留作练习:)

例如，给定 N = 10 和开关 = [3,6]，我们有:

   3-0, 6-3, 10-6
   on , off, on

(skip every other value)
    <- - - - - -
Reversed prefix sums 1:
   7  , (4),  4
Reversed prefix sums 2:
   (3) , 3  , (0)

当我们遍历输入时，尝试每个 block ，我们的选择不会像您建议的那样影响左边的总和。我们可以从我们的前缀中得到右边的总和:

block 0: since it's previously `on`
   we'd place it towards the end
   at 2, resulting in

   2-0 (reduced from 3-0) +
   (0 for 3-2 time units when it's off) +
   3 (prefix sum in the next block)
   = 5

block 1: since it's previously `off`
   we'd place it towards the start
   at 4, resulting in

   3 (accumulated) +
   6-4 for when it's now on +
   0 (prefix sum in the next block)
   = 5

block 2: since it's previously `on`
   we'd place it towards the end
   at 9, resulting in

   3 (accumulated) +
   9-6 (reduced from 10-6) +
   (0 for 10-9 time units when it's off) +
   = 6