Учитывая N человек, некоторые из которых являются врагами, найдите количество интервалов без врагов.

Question

Друг задал мне эту проблему как вызов, и я попытался найти такую ​​проблему на LeetCode, но, к сожалению, не смог.

Вопрос

Учитывая В строке людей, пронумерованных от 1 до N, и в списке пар из M врагов найдите общее количество подстрок с людьми, в которых нет двух человек, являющихся врагами.

Пример: N = 5, enemies = [[3,4], [3,5]]

Ответ: 9

Пояснение: Эти непрерывные подынтервалы:

[1,1], [2,2], [3,3], [1,2], [2,3], [1,3], [4,4], [4,5], [5,5]

Мой подход

Мы определяем неконфликтный интервал как непрерывный интервал от (включительно) [a,b], где в этом интервале нет двух врагов.

Работа в обратном направлении, если я знаю, что существует неконфликтный интервал от [1,3], как в приведенном выше примере, я знаю, что количество смежных интервалов между этими двумя числами равно n(n+1)/2, где n - длина интервала. В этом случае длина интервала составляет 3, поэтому существует 6 интервалов между (включительно) [1,3], которые считаются.

Расширение этого logi c, если у меня есть список все неконфликтующие интервалы , тогда ответ будет просто суммой (n_i*(n_i+1))/2 для каждой длины интервала n_i.

Тогда все, что мне нужно сделать, это найти эти интервалы. Вот где я застрял.

Я не могу придумать подобную проблему программирования. Это похоже, но противоположно тому, о чем просит проблема Merge Interval в leetcode. В этой задаче нам вроде как даны хорошие интервалы и просят их объединить. Здесь нам плохо.

Есть какие-нибудь указания?

РЕДАКТИРОВАТЬ: Лучшее, что я мог придумать:

Это работает?

Итак, давайте определим max_enemy[i] как самого большого врага, который меньше определенного person i, где i - это обычный [1,N]. Мы можем сгенерировать это значение за O(M) время, просто используя следующий l oop:

max_enemy = [-1] * (N+1) # -1 means it doesn't exist
for e1, e2 in enms:
    e1, e2 = min(e1,e2), max(e1, e2)
    max_enemy[e2] = max(max_enemy[e2], e1)

Затем, если мы go через массив человека, сохраняя скользящее окно. Скользящее окно закрывается, как только мы находим человека i, у которого есть: max_enemy[i] < i. Таким образом, мы знаем, что включение этого человека нарушит наш непрерывный интервал. Итак, теперь мы знаем, что наш интервал равен [s, i-1], и можем проводить вычисления. Сбрасываем s=i и продолжаем.

Вот визуализация того, как это работает визуально. Мы рисуем путь между любыми двумя врагами:

N=5, enemies = [[3,4], [3,5]]

1   2   3   4  5
        |   |  |
        -----
        |      |
        --------

EDIT2: Я знаю, что это не работает для N=5, enemies=[[1,4][3,5]], в настоящее время работает над исправлением, все еще застрял

Answer 1

Вы можете решить это за O (M log M) время и O (M) пространство.

Пусть ENDINGAT (i) будет количеством интервалов без врагов, заканчивающихся в позиции / человеке i. Это также размер самого большого интервала отсутствия врагов, заканчивающегося на i.

Ответ, который вы ищете, представляет собой сумму всех ENDINGAT (i) для каждого человека i.

Пусть NEAREST (i ) быть ближайшим врагом человека i, который предшествует человеку i. Пусть это будет -1, если у i нет предыдущих врагов.

Теперь мы можем написать простую формулу для вычисления всех ENDINGAT (значений):

ENDINGAT (1) = 1, поскольку существует только один интервал, заканчивающийся на 1. Для больших значений:

ENDINGAT (i) = MIN (ENDINGAT (i-1) +1, i-NEAREST (i))

Итак, это очень легко вычислить все ENDINGAT (i) по порядку, если мы можем иметь все NEAREST (i) в порядке. Чтобы получить это, все, что вам нужно сделать, это отсортировать пары врагов по старшему члену. Затем для каждого i вы можете пройтись по всем парам, оканчивающимся на i, чтобы найти ближайшую.

Вот и все - это оказывается довольно легко. Во времени преобладает время O (M log M), необходимое для сортировки пар врагов, если только N не намного больше, чем M. В этом случае вы можете пропустить прогоны ENDINGAT для людей, у которых не было предыдущих врагов, рассчитывая их влияние на математически сложить.

Answer 2

Есть отличный визуальный способ увидеть это!

Вместо того, чтобы фокусировать линию, давайте посмотрим на матрицу пар игроков. Если i i и j являются врагами, тогда эффект этого вражеского оружия состоит в том, чтобы исключить из рассмотрения (1) этот интервал и (2) любой интервал, строго превышающий его. Поскольку противник симметричен c, мы можем просто смотреть на верхнюю правую половину матрицы и диагональ; мы будем использовать символы

• «X», чтобы обозначить, что пара является врагами,
• «*», чтобы указать, что пара была скрыта парой. врагов, и
• «%» в нижней половине, чтобы отметить его как не часть верхней половины матрицы.

Для двух примеров в вашем коде обратите внимание соответствующие им матрицы:

# intervals:  9                   # intervals:  10

 0   1   2   3   4                 0   1   2   3   4      
------------------------          ------------------------
             *   *   | 0                        *   *   | 0           
 %           *   *   | 1            %           X   *   | 1           
 %   %       X   X   | 2            %   %           X   | 2           
 %   %   %           | 3            %   %   %           | 3           
 %   %   %   %       | 4            %   %   %   %       | 4           

Наивное решение, представленное ниже, решает проблему во O(N^2 M) времени и O(N^2) пространстве.

def matrix(enemies):
    m = [[' ' for j in range(N)] for i in range(N)]
    for (i,j) in enemies:
        m[i][j] = 'X' #Mark Enemiship
        # Now mark larger intervals as dead.
        for q in range(0,i+1):
            for r in range(j,N):
                if m[q][r] == ' ':
                    m[q][r] = '*'

    num_int = 0
    for i in range(N):
        for j in range(N):
            if(j < i):
                m[i][j] = '%'
            elif m[i][j] == ' ':
                num_int+=1

    print("# intervals: ", num_int)
    return m

Чтобы убедиться в этом, вот матрицы, где

1. игрок 2 - это враги с самим собой, так что есть барьер, и есть две меньшие версии головоломки на интервалах [0,1] и [3,4], каждая из которых допускает 3 подинтервала)
2. Каждый игрок является противником, а два человека слева от него, так что разрешены только интервалы длины (1 или 0) (из которых 4 + 5 = 9 интервалов)

# intervals:  6                   # intervals:  9

 0   1   2   3   4                 0   1   2   3   4      
---------[===========+              --------[============+
         *   *   *  || 0                    X   *   *  || 0           
 %       *   *   *  || 1            %           X   *  || 1           
 %   %   X   *   *  II 2            %   %           X  II 2           
 %   %   %           | 3            %   %   %           | 3           
 %   %   %   %       | 4            %   %   %   %       | 4           

Сложность: математически такая же, как сортировка списка или проверка того, что он отсортирован . то есть O(M log M) в худшем случае и O(M) пространство для сортировки, и, по крайней мере, O(M) время в лучшем случае, чтобы распознать, отсортирован ли список. Бонус: это также отличный пример, иллюстрирующий способность взглянуть на личность как на проблему, а не на ее решение. Такой взгляд на проблему также поможет найти более разумные решения. Мы явно можем сделать намного лучше, чем код, который я дал выше ...

Мы явно закончили бы, например, если бы мы могли подсчитать количество незатененных точек, которое является площадью наименьшего выпуклого многоугольник, покрывающий вражеские корабли, вместе с двумя граничными точками. (Найти две дополнительные точки можно за O(M) времени.) Теперь, вероятно, это не проблема, которую вы можете решить во сне, но, к счастью, проблема поиска выпуклой оболочки настолько естественна, что алгоритмы .

В частности, Сканирование Грэма может сделать это за O(M) время, пока нам дадут пары врагов так что одна из их координат будет отсортирована. Еще лучше, если у нас есть набор точек в выпуклой оболочке, площадь можно рассчитать, разделив ее не более чем на M прямоугольников, выровненных по оси. Следовательно, если вражеские пары отсортированы, вся проблема может быть решена за O(M) время. Имейте в виду, что M может быть значительно больше, чем N, и нам даже не нужно хранить N чисел в массиве! Это соответствует арифметике c, предложенной для пропуска строк в другом ответе на этот вопрос.

Если они не отсортированы, другие алгоритмы выпуклой оболочки дают время выполнения O(M log M) с пробелом O(M), как указано @ Решение Мэтта Тиммерманса . Фактически, это общая нижняя оценка! Это можно показать с помощью более сложной геометрической c редукции: если вы можете решить задачу, то вы можете вычислить сумму высот каждого числа, умноженную на его расстояние до «нового нуля», агентов, удовлетворяющих условию j+i = N. Эту сумму можно использовать для вычисления расстояний до диагональной линии, чего достаточно для сортировки списка чисел за O(M) время - проблему, которая не может быть решена менее чем за O(M log M) время для состязательных входов.

Ах, так почему же мы можем получить решение O(N + M), вручную выполнив эту интеграцию, как это явно сделано в другом решении? Это потому, что мы можем отсортировать числа M, если знаем, что они попадают в N ячейки, по Bucket Sort .

Спасибо за то, что поделились головоломкой!