Алгоритм нахождения общего времени простоя данного массива времени начала / окончания

Question

Скажем, у вас есть время начала и окончания.

Также вам предоставляется массив заданий, описываемых временем их начала и окончания. Эти задания могут перекрываться (т. Е. Одновременно может выполняться несколько заданий). Мне нужно найти способ определить, сколько времени было потрачено вхолостую и не выполнять какую-либо работу.

Конечно, если в одно и то же время может выполняться только одно задание, я могу просто вычесть время выполнения каждого задания, но часть с перекрытием поставила меня в тупик.

Answer 1

Отсортируйте время, а затем просмотрите его по порядку.
Если время является временем начала, добавьте 1 к числу запущенных задач.
Если это время остановки, вычтите 1.
Следите за тем, сколько времени занимает количество заданий, равное 0.

Answer 2

Поместите все время начала и окончания в один массив, отметив их как время начала или окончания. Сортировать массив по времени. Теперь переберите отсортированный список, ведя подсчет количества выполненных заданий:

• увеличение счетчика при чтении времени начала
• уменьшение счетчика при чтении времени окончания

Всякий раз, когда вы увеличиваете от нуля до единицы, добавьте (current_time - previous_time) к общему времени простоя. Не забудьте также в специальном случае начать и закончить, если необходимо.

Answer 3

Вот немного другой подход. Первая часть носит иллюстративный характер.

Создание массива целых, представляющих полную временную шкалу всех заданий. Это может быть в часах, минутах или как вам нужно. Я возьму часы. Найдите самое раннее время начала и самое позднее время окончания, чтобы установить размер массива. Инициализировать все элементы в ноль.

Перебирайте каждое задание, увеличивая счетчик на временной шкале для каждого часа выполнения задания. Таким образом, если задание выполняется с 15:00 до 17:00, то это два часа, поэтому вы должны увеличить интервал 3 часа и 4 часа, чтобы указать, что задание выполнялось в эти часы.

Цикл по временной шкале, подсчет количества нолей, с которыми вы сталкиваетесь. Это те временные интервалы, когда работа не выполнялась.

Теперь, если вы понимаете это, довольно легко избавиться от массива. Вместо создания (большого) массива, просто отслеживайте время начала и окончания всей временной шкалы. Для каждого часа в этом диапазоне просматривайте все ваши задания и смотрите, сколько из них запущено за это время. Любые, которые являются нулем, являются простоями.

Answer 4

У вас есть куски занятого времени, когда выполняется одно или несколько заданий. Время простоя - это сумма промежутков времени между занятыми кусками. Псевдокод:

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

Примечание. Для простоты я пропустил код для обработки первого элемента.

Answer 5

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