시작/끝 시간의 배열 주어진 총 유휴 시간을 찾기위한 알고리즘

Question

시작과 종료 시간이 주어 졌다고합시다.

또한 시작일과 종료일로 설명되는 일련의 작업이 제공됩니다. 이러한 작업은 겹칠 수 있습니다 (예 : 한 번에 여러 작업이 실행될 수 있음). 얼마나 많은 시간을 유휴 상태로 보내고 어떤 일을하지 않을지 결정할 방법을 찾아야합니다.

물론 하나의 작업 만 언제든지 실행할 수 있다면 각 작업의 실행 시간을 뺄 수는 있지만 겹침 부분은 저를 곤두박질로 만듭니다.

Answer 1

, 하나의 배열로 모든 시작 시간과 종료 시간을 넣어로 태그 시작 또는 종료 시간. 배열을 시간순으로 정렬하십시오. 지금 실행중인 얼마나 많은 일자리의 수 유지, 정렬 된 목록을 반복 : 종료 시간을 읽을 때 카운터를 감소시키는 시작 시간

을 읽을 때 카운터를 증가

• 을

때마다 0에서 1로 증가하고, 총 유휴 시간에 (current_time - previous_time)을 더합니다. 필요한 경우 시작과 끝이라는 특별한 경우도 기억하십시오.

Answer 2

시간을 정렬 한 다음 순서대로 실행하십시오.
시간이 시작 시간 인 경우 실행중인 작업 수에 1을 더하십시오. 멈출 시간 인 경우
, 작업의 수를 때 1
가 얼마나 많은 시간을 추적 빼기 0

Answer 3

다음은 약간 다른 접근 방식입니다. 첫 번째 부분은 설명을위한 것입니다.

모든 작업의 ​​전체 타임 라인을 나타내는 int 배열을 만듭니다. 시간, 분 또는 기타 필요한 시간이 될 수 있습니다. 시간이 걸릴거야. 배열의 크기를 설정하는 가장 빠른 시작 시간과 마지막 종료 시간을 찾습니다. 모든 원소를 0으로 초기화하십시오.

각 작업을 반복하면서 작업이 실행되는 시간당 타임 라인에서 카운터를 증가시킵니다. 그래서 일이 오후 3시에서 오후 5 시까 지 실행된다면 2 시간이됩니다. 그래서 3 시간과 4 시간 슬롯을 증가시켜 그 시간 동안 작업이 실행 중임을 나타냅니다.

타임 라인을 반복하면서 발생하는 0의 수를 유지합니다. 그것들은 아무 작업도 실행하지 않는 시간 슬롯입니다.

이제 이해한다면 쉽게 배열을 제거 할 수 있습니다. (potintially large) 배열을 만드는 대신 전체 타임 라인의 시작과 끝 시간을 추적하십시오. 해당 범위의 각 시간마다 모든 작업을 반복하고 그 시간 동안 실행중인 작업 수를 확인합니다. 0 인 것은 유휴 시간입니다.

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

참고 : 단순화하기 위해, 나는 첫 번째 요소를 처리하는 코드를 떠났다.