Подсчет активных задач по времени запуска и продолжительности в C ++ - PullRequest
Новая
       37

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

0 голосов
/ 16 сентября 2018

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

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

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

1 Ответ

0 голосов
/ 16 сентября 2018

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

В вашем игрушечном вводе у вас есть: 

2 5
4 23
7 4

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

2 7
4 27
7 11

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

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

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

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

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

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

...