Два массива, один со временем, другой со временем из чего-то

Question

Допустим, у нас есть 2 массива, один из которых (т.е. A) содержит время, когда объект i войдет в комнату, а другой (т.е. B) содержит время i уйдет.Ни один из них никоим образом не отсортирован, и их содержимое является Действительными числами .

Например, объект 3 имеет: A [3] = 0,785 и B [3] = 4,829.

Как бы вы в O (nlogn) нашли максимальное количество объектов в комнате в любой момент времени t?

Answer 1

Вы можете попробовать это:

• инициализировать число объектов как ноль
• отсортировать оба массива
• , в то время как в любом массиве остались элементы
  • определить, какое первое значение массива меньше
  • , если первое значение в "enter" меньше, увеличить число объектов и выдать это значение
  • , если первое значение в "exit" меньше, уменьшите число объектов и вытолкните это значение
  • проверьте, не нашли ли вы новое максимальное количество объектов

Если вы не можете "вытолкнуть" элементы извместо массивов вы можете использовать две индексные переменные;также вам нужно будет добавить случаи, когда один из массивов уже пуст.

Сортировка имеет O (nlogn), а следующий цикл имеет O (2 * n), таким образом, O (nlogn) всего.

Answer 2

Получить все время из обоих массивов и составить пары {time from A or from B; f = +1 for A/ -1 for B}

Сортировать массив всех пар по временному ключу (в случае равенства +1 идет перед -1)

Создать count = 0

Перемещение массива пар, добавление значения f к count.

Максимальное значение count - это "максимальное количество объектов в комнате"

Пример:

  A = [2, 5], B = [7, 9]
  pairs = (2,1),(5,1),(7,-1),(9,-1)
  count = 1, 2, 1, 0 
  maxcount=2 at interval 5..7