給定開始/結束時間陣列找到總空閒時間的算法

Question

假設您給出開始和結束時間。

此外，您還可以獲得一系列的工作，按其開始和結束時間描述。這些作業可能會重疊（即可能同時運行多個作業）。我需要找到一種方法來確定花了多少時間閒置和不運行任何工作。

當然，如果只有一個工作可以隨時運行，我可以將每個工作的運行時間減去，但重疊部分讓我難倒了。

Answer 1

把所有的開始和結束時間爲一個單一的陣列，它們標記爲無論是開始還是結束時間。按時間排序數組。現在，通過排序列表循環，保持多少作業運行的計數：

• 閱讀的開始時間
• 當遞減計數器讀數的結束時間時增加計數器

每當您從零增加到1，將（current_time - previous_time）添加到總空閒時間。如有必要，還要記住特殊情況的開始和結束。

Answer 2

對時間進行排序，然後按順序排列。
如果時間是開始時間，請將運行的任務數加1。
如果是停止時間，減去1
保持跟蹤有多少時間時，任務數爲0

Answer 3

這是一個稍微不同的方法。第一部分是爲了說明的目的。

創建一個表示所有作業的完整時間軸的整數的數組。這可以在幾小時，幾分鐘或任何你需要的。我會假設幾個小時。查找最早的開始時間和最近的結束時間來設置數組的大小。初始化所有元素爲零。

循環遍歷每個作業，在作業正在運行的每個小時的時間軸上遞增計數器。因此，如果一項工作從下午3點到下午5點運行，那就是兩個小時，所以您應該增加3小時和4小時的時間段，以表明在這段時間內工作正在運行。

循環遍歷時間軸，記錄您遇到的零點數。那些是沒有工作正在運行的時間段。

現在，如果你明白，擺脫陣列是相當容易的。而不是創建一個（大大小小的）數組，只需跟蹤整個時間線的開始和結束時間。對於該範圍內的每個小時，循環顯示所有工作，並查看在此期間有多少人正在運行。任何零都是空閒時間。

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

當有一個或多個作業正在運行時，您有大量的繁忙時間。 空閒時間是繁忙組塊之間時間跨度的總和。 僞代碼：

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 
    } 
} 

注意：爲了簡單起見，我離開了的代碼來處理第一個元素。