Thuật toán để tìm tổng thời gian không hoạt động cho mảng của thời gian bắt đầu/kết thúc

Question

Giả sử bạn có thời gian bắt đầu và kết thúc.

Bạn cũng được cung cấp một loạt công việc, được mô tả theo thời gian bắt đầu và kết thúc của họ. Các công việc này có thể trùng lặp (nghĩa là có thể có nhiều công việc cùng một lúc). Tôi cần phải tìm một cách để xác định bao nhiêu thời gian đã được nhàn rỗi và không chạy bất kỳ công việc.

Tất nhiên, nếu chỉ có một công việc có thể chạy bất cứ lúc nào, tôi chỉ có thể trừ đi thời gian chạy của mỗi công việc, nhưng phần chồng chéo đã khiến tôi bối rối.

Answer 1

Đặt tất cả bắt đầu và kết thúc vào một mảng duy nhất, gắn thẻ chúng như thời gian bắt đầu hoặc kết thúc. Sắp xếp mảng theo thời gian. Bây giờ lặp qua danh sách được sắp xếp, giữ một đếm có bao nhiêu công việc đang chạy theo:

• incrementing quầy khi đọc một thời gian bắt đầu
• decrementing bộ đếm khi đọc một thời gian cuối

Bất cứ khi nào bạn tăng từ 0 lên 1, thêm (current_time - previous_time) vào tổng thời gian rỗi. Cũng nên nhớ trường hợp đặc biệt bắt đầu và kết thúc nếu cần.

Answer 2

Sắp xếp thời gian và sau đó chạy qua chúng theo thứ tự.
Nếu thời gian là thời gian bắt đầu, hãy thêm 1 vào số lượng tác vụ đang chạy.
Nếu nó là một thời gian dừng, trừ 1.
Theo dõi bao nhiêu thời gian có khi số lượng các nhiệm vụ là 0.

Answer 3

Đây là cách tiếp cận hơi khác. Phần đầu tiên là nhằm mục đích minh họa.

Tạo một mảng ints đại diện cho toàn bộ dòng thời gian của tất cả công việc. Điều này có thể bằng giờ, phút, hoặc bất cứ điều gì bạn cần. Tôi sẽ giả định giờ. Tìm thời gian bắt đầu sớm nhất và thời gian kết thúc mới nhất để đặt kích thước của mảng. Khởi tạo tất cả các phần tử về 0.

Lặp qua từng công việc, tăng bộ đếm trong dòng thời gian cho mỗi giờ công việc đang chạy. Vì vậy, nếu một công việc chạy từ 3 giờ chiều đến 5 giờ chiều, đó là hai giờ, vì vậy bạn sẽ tăng thời gian 3 giờ và 4 giờ để chỉ ra rằng một công việc đang chạy trong những giờ đó.

Lặp qua dòng thời gian, giữ số lượng số lượng bạn gặp phải. Đó là những khoảng thời gian mà không có công việc nào đang chạy.

Bây giờ, nếu bạn hiểu điều đó, thật dễ dàng để loại bỏ mảng đó. Thay vì tạo một mảng (potintially large), chỉ cần theo dõi thời gian bắt đầu và kết thúc của toàn bộ dòng thời gian. Đối với mỗi giờ trong vòng lặp phạm vi đó thông qua tất cả các công việc của bạn và xem có bao nhiêu công việc đang chạy trong thời gian đó. Bất kỳ số nào bằng 0 đều là thời gian không hoạt động.

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

Bạn có nhiều thời gian bận rộn, khi một hoặc nhiều công việc đang chạy. Thời gian nhàn rỗi là tổng thời gian kéo dài giữa các khối bận. Mã giả:

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

Lưu ý: Để đơn giản, tôi đã bỏ qua mã để xử lý phần tử đầu tiên.