Интервью Вопрос: Вставьте переключатель, чтобы увеличить время, которое лампочка тратит на

Question

Вот формулировка проблемы:

У вас есть лампочка на интервале N секунд, где дается N.В момент времени 0 лампочка включается, а в момент времени N она выключается независимо от каких-либо переключателей.Время от времени 1 до времени N-1 у вас есть максимум N-2 переключателей в виде массива, называемого переключателями, которые поворачивают лампочку в противоположность тому, что она есть на данный момент, т.е. если она включена, она выключится и наоборот,Например, предположим, что N = 8 и переключатели = [1,2].Лампочка включится во время 0, выключатель во время 1 выключит ее, выключатель во время 2 включит ее, и она будет оставаться до времени 8, когда она выключится.Следовательно, время, в течение которого оно остается, равно 1-0 + 8-2 = 7.

Теперь предположим, что вы должны вставить переключатель в этот интервал, где он еще не присутствует.Каково максимальное время, в течение которого лампочка остается включенной после включения переключателя.Например, в приведенном выше случае решение будет 6, поскольку при включении переключателя в момент времени 7 время, затрачиваемое лампочкой, будет максимальным.Так как 1-0 + 7-2 = 6, ответ - 6.

Я решил проблему, используя грубое решение, полагая, что если вы вставите переключатель в момент времени k, то состояниялампочки до того, как это не будет затронуто, и состояния лампочки от времени k до времени N будут обратными, и, следовательно, вы можете найти время, которое она проводит после времени k, по (N - k) - t, гдеt - это время, которое он провел бы от времени k до N без вставленного переключателя.Следовательно, я могу рассчитать время, которое лампочка будет тратить на каждую временную позицию вставленного переключателя, и максимизировать его.Однако, так как вычисление времени, которое тратит лампочка, является операцией O (n), и я перебираю все возможные позиции, мое решение - O (n ^ 2), и это привело к истечению времени ожидания моего кода для некоторых тестовых случаев.

Может кто-нибудь предложить лучшее решение?

Answer 1

Если мы вставляем в ранее включенный блок, то, как в вашем примере, мы хотели бы вставить его как можно ближе к концу этого периода on.И если мы вставим в ранее off блок, мы поместим его как можно ближе к началу этого периода, чтобы максимизировать новое время on этого блока.

Чтобы вычислить полезность любоговыбор в O(1), мы можем ссылаться на шахматные префиксные суммы, накопленные в конце массива.(Как прокомментировал выше Нико Шертлер, мы могли бы динамически выполнить весь расчет за один проход с конца с постоянным пробелом - оставив его в качестве упражнения:)

Например, для 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 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