Подсчет активных задач по времени начала и продолжительности в C++

Question

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

3
2 5
4 23
7 4

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

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

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

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

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

Answer 1

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

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

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 хранить ваши структуры, а не простой массив. Таким образом, вы бы также избежали динамического выделения памяти, поскольку вектор позаботится об этом автоматически.