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

Question

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

Входные данные состоят из набора задач, заданных в порядке возрастания времени запуска, и каждая задача имеет определенную продолжительность.
Первая строка — это количество задач, например

Это означает, что есть 3 задачи. Первый начинается в момент времени 2 и заканчивается в 7 (2 + 5). Второй начинается в 4, заканчивается в 27. Третий начинается в 7, заканчивается в 11.
Мы предполагаем, что каждая задача запускается, как только она готова, и не нужно ждать освобождения процессора или чего-либо еще.
Это означает, что мы можем отслеживать количество активных задач:

Time       #tasks
0 - 2        0
2 - 4        1
4 - 11       2
11 - 27      1

Мне нужно найти 2 номера:

Максимальное количество активных заданий в любой момент времени (в данном случае 2) и
Среднее количество активных заданий за всю продолжительность вычисляется здесь как:

[0 * (2-0) + 1 * (4-2) + 2 * (11-4) + 1 * (27-11)] / 27

За это,
Сначала я нашел время, когда все задачи подошли к концу, используя следующий код:

#include "stdio.h"#include "stdlib.h"
typedef struct
{
long int start;
int dur;
} task;

int main()
{
long int num_tasks, endtime;
long int maxtime = 0;
scanf("%ld",&num_tasks);
task *t = new task[num_tasks];
for (int i=0;i<num_tasks;i++)
{
scanf("%ld %d",&t[i].start,&t[i].dur);
endtime = t[i].start + t[i].dur;
if (endtime > maxtime)
maxtime = endtime;
}
printf("%ld\n",maxtime);
}

Можно ли это сделать с помощью очередей приоритетов, реализованных в виде кучи?

0

c++event-driven heap priority-queue

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Ваш вопрос довольно широкий, поэтому я просто дам вам ответ на тизер, который, надеюсь, поможет вам начать, пытаясь ответить на вашу первую часть вопроса, с не обязательно оптимизированным решением.

В вашей игрушке, у вас есть:

2 5
4 23
7 4

таким образом, вы можете вычислить и сохранить в массиве имеющихся у вас структур время окончания задачи, а не ее продолжительность, для последующего использования. Это дает в виде массива, как это:

2 7
4 27
7 11

Ваш массив уже отсортирован (потому что входные данные даны в таком порядке) по времени начала, и это полезно. использование std::sort отсортировать массив, если это необходимо.

Посмотрите, как вы можете проверить время окончания первой задачи в сравнении с временем начала других задач. При правильном сравнении вы можете определить количество активных задач вместе с первой задачей. Проверка того, больше ли время окончания первой задачи, чем время начала второй задачи, если true, означает, что эти две задачи активны вместе в какой-то момент.

Тогда вы бы сделали то же самое для сравнения первого с третьим заданием. После этого вы узнаете, сколько заданий было активным по отношению к первому заданию.

После этого вы будете следовать той же процедуре для второго задания и так далее.

Собрав все это вместе в коде, мы получим:

#include "stdio.h"#include "stdlib.h"#include <algorithm>

typedef struct {
int start;
int dur;
int end;
} task;

int compare (const task& a, const task& b) {
return ( a.start < b.start );
}

int main() {
int num_tasks;
scanf("%d",&num_tasks);
task *t = new task[num_tasks];
for (int i=0;i<num_tasks;i++) {
scanf("%d %d",&t[i].start,&t[i].dur);
t[i].end = t[i].start + t[i].dur;
}
std::sort(t, t + num_tasks, compare);
for (int i=0;i<num_tasks;i++) {
printf("%d %d\n", t[i].start, t[i].end);
}
int max_noOf_tasks = 0;
for(int i = 0; i < num_tasks - 1; i++) {
int noOf_tasks = 1;
for(int j = i + 1; j < num_tasks; j++) {
if(t[i].end > t[j].start)
noOf_tasks++;
}
if(max_noOf_tasks < noOf_tasks)
max_noOf_tasks = noOf_tasks;
}
printf("Max. number of active tasks: %d\n", max_noOf_tasks);
delete [] t;
}

Выход:

2 7
4 27
7 11
Max. number of active tasks: 2

Теперь удачи со второй частью вашего вопроса.

PS: так как это C ++, вы могли бы использовать std::vector хранить ваши структуры, а не простой массив. Таким образом, вы бы также избежали динамического выделения памяти, поскольку вектор позаботится об этом автоматически.

0