Максимальное количество задач, выполняемых параллельно?

Question

Проблема:

Нам дано множество из п задач, каждая из которых имеет целое время начала и время окончания . Каково максимальное количество задач, выполняемых параллельно в в любое время?

Алгоритм должен работать в O (n log n) время.

Это назначение школы, так что я не нужен прямой ответ, но любые фрагменты кода приветствуются, пока они находятся в Java или Scala (уступке предполагается записать в Скале.)

Некоторые подсказки говорят, что я должен использовать очереди Priority. Я прочитал документацию, но я не уверен, как их использовать, поэтому любые фрагменты кода приветствуются.

Вводимые данные могут быть, например, Array[Pair[Int,Int]] = Array((1000,2000),(1500,2200)) и т. Д.

Я действительно пытаюсь установить порядок очередей приоритетов, поэтому, если ничего другого, я надеюсь, что кто-то может мне помочь в этом.

PS: Предполагается, что очередь приоритетов будет инициализирована PriorityQueue() (ord).

Редактировать: я придумал решение с использованием очередей приоритетов, но спасибо за все ответы. Вы, ребята, помогли мне разобраться в логике!

Answer 1

Soln без использования очереди приоритетов.

Рассмотрим множество задач следующим образом:

[(1,2), (1,5), (2,4), ....] // (a,b) : (start_time, end_time) 

Шаг 1: Construct массив с учетом start_time и end_time вместе.

[1,2,1,5,2,4....] 

Шаг 2: Поддерживать другой массив, чтобы узнать, является ли время в индексе я это start_time или END_TIME

[S,E,S,E,S,E...] // S:Start_Time, E:End_Time 

Шаг 3: Сортировка первого массива. И обязательно измените индекс в другом массиве соответственно.

Этап 4: Поддерживать две переменные, parallel_ryt_now и max_parallel_till_now. И пройти второй массив следующим образом:

for i in 1:len(second_array): 
    if(second_array[i] == "S"): 
     parallel_ryt_now ++ 
    else 
     parallel_ryt_now -- 
    if parallel_ryt_now > max_parallel_till_now: 
      max_parallel_till_now = parallel_ryt_now 

Логик:

Хотя обход отсортированного массива, когда и сталкивается с start_time, это означает, что задача началась.Таким образом, приращение на parallel_ryt_now и когда и столкнулись с end_time, означает, что задача завершена, таким образом, уменьшать parallel_ryt_now.

Таким образом, в каждый момент parallel_ryt_now вар хранит параллельно запущенные задачи.

Время Сложность = Сортировать + траверс = O(nlogn) + O(n) = O(nlogn)

Space Сложность = O(n) (Чтобы сохранить дополнительный массив для информации о том времени, в индексе i является start_time или end_time)

I надеюсь, что это помогло.