並行して実行されているタスクの最大量は？

Question

問題：

我々はそれぞれが整数、時間と 終了時刻を開始有する、n個のタスクのセットを与えられています。任意の時間に並列実行されているタスクの最大量は ですか？

アルゴリズムは、O（n log n）時間で実行する必要があります。

限り、彼らは、JavaやScalaであるとして歓迎され、私は直接の回答が、任意のコードスニペットを必要としないので、これは学校の割り当てです（割り当てはScalaで書かれることになって。）

一部ヒントのうち、私は優先度キューを利用すべきだと言います。私はドキュメンテーションを読んでいますが、実際の使用方法は分かりませんので、コードスニペットは大歓迎です。

入力データは、たとえば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：一緒start_timeとend_timeを考慮配列を構築物を以下のように

は、タスクの配列を考えます。

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

ステップ2：最初の配列をソートする：インデックスで時間iがSTART_TIMEであるかどうかを知っているか

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

ステップ3をEND_TIMEする別の配列を維持します。それに応じて、別の配列のインデックスを必ず変更してください。

ステップ4：2つの変数、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 

ロジック：ソートされた配列を横断しながらuはstart_timeが発生したとき

を、そのタスクが開始したことを意味します。したがって、parallel_ryt_nowをインクリメントし、end_timeに遭遇したときは、タスクが完了したことを意味し、したがってparallel_ryt_nowを減らします。

このように、毎晩、parallel_ryt_nowは並列実行タスクを格納します。

時間計算 =ソート+トラバース= O(nlogn) + O(n) = O(nlogn)

スペース複雑 = O(n)（インデックスiで時間がstart_timeかend_timeであるかどうかについての情報のための余分な配列を格納するために）

Iそれが助けてくれることを願う