在 C++ 中使用开始时间和持续时间计算活动任务

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

这可以使用作为堆实现的优先级队列来完成吗？

Answer 1

你的问题相当宽泛，所以我只给你一个简单的答案，希望它能帮助你开始，尝试用一个不一定优化的解决方案来回答你问题的第一部分。

在你的玩具输入中，你有：

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 来存储您的结构，而不是普通数组。这样你也可以避免动态内存分配，因为向量会自动为你处理。

在 C++ 中使用开始时间和持续时间计算活动任务

Counting active tasks using start time and duration in C++

c++

heap

priority-queue

event-driven