与えられた開始時間と終了時間の合計アイドル時間を求めるアルゴリズム

Question

開始時刻と終了時刻が与えられたとします。

また、開始時間と終了時間で記述された一連のジョブが表示されます。これらのジョブは重複する（つまり、一度に複数のジョブが実行される可能性があります）。どのくらいの時間がアイドルに費やされていて、何の仕事もしていないと判断する方法を見つける必要があります。

もちろん、1つのジョブしか実行できない場合は、各ジョブの実行時間を差し引いても問題はありませんが、重複部分が私を困惑させてしまいます。

Answer 1

、単一のアレイにすべての開始時刻と終了時刻を入れて、それらをタグ付け開始時刻または終了時刻のいずれか。配列を時間順に並べ替えます。

たび終了時刻を読み込むときにカウンタをデクリメント

開始時刻を読み取る際にカウンタを増分

• ：今で実行されているどのように多くのジョブの数を保ち、ソートされたリストを繰り返し処理0から1へ増やし、合計アイドル時間に（current_time - previous_time）を加算します。必要に応じて、開始と終了を特別な場合も忘れないでください。

Answer 2

時間をソートし、順番に実行します。
時間が開始時刻の場合は、実行中のタスクの数に1を加算します。それは停止時間がある場合は
、タスクの数があるときに1
があるどのくらいの時間を追跡引く0

Answer 3

ここでは、少し異なるアプローチです。最初の部分は説明のためのものです。

すべてのジョブの完全なタイムラインを表すintの配列を作成します。これは、何時間でも何分でもかまいません。私は何時間もかかるだろう。配列のサイズを設定するために、最も早い開始時刻と最後の終了時刻を見つけます。すべての要素をゼロに初期化します。

各ジョブをループし、ジョブが実行されている時間ごとにタイムラインのカウンタを増分します。したがって、ジョブが午後3時から午後5時まで実行されている場合は2時間ですので、3時間と4時間のスロットを増分してその時間内にジョブが実行されたことを示します。

タイムラインをループし、発生するゼロ数をカウントします。これらは、ジョブが実行されていないタイムスロットです。

これを理解すれば、配列を取り除くのはかなり簡単です。 （potintially large）配列を作成する代わりに、タイムライン全体の開始時刻と終了時刻を追跡するだけです。その範囲内の各時間ごとに、すべてのジョブをループし、その時間中に実行されている数を確認します。ゼロであるものは、アイドル時間です。

Answer 4

Sort the jobs based on their end times. 

Jobs<startTime,EndTime>[] = contains the Sorted list. 

Take first Job in the list 
Jobs[0] 

intialize: 
    EndTime = Job[0].EndTime 
    StartTime = Job[0].StartTime 
    idleTime =0; 

For i = 1 till Jobs.size 
{ 
    if (Jobs[i].EndTime >= StartTime) 
    { 
     //Do nothing, its overlapping 
    } 
    else 
    { //Previoys Job time doesnot overlap, so get the idle time. 
     idleTime += (StartTime -Jobs[i].EndTime); 
    } 

    StartTime = Jobs[i].StartTime; 
    EndTime = Jobs[i].EndTime; 
} 

Answer 5

あなたは、1つまたは複数のジョブが実行されているとき、忙しい時間のチャンクを持っています。 アイドル時間は、ビジーチャンク間の時間スパンの合計です。 擬似コード：

idle_time = 0 
sort jobs by start time 
foreach job in jobs 
{ 
    if (job.start > current_chunk.end) 
    { 
    idle_time += job.start - current_chunk.end 
    } 
    if (job.end > current_chunk.end) 
    { 
    current_chunk.end = job.end 
    } 
} 

注：簡単にするために、私は最初の要素を処理するコードを残しました。