在C++中使用开始时间和持续时间计数活动任务
输入由一组按开始时间的递增顺序给定的任务组成，每个任务都有一定的持续时间关联。第一行是任务数，例如
3
2 5
4 23
7 4这意味着有三个任务。第一个开始于时间2，结束于7 (2+5)。第二名从4点开始，27点结束。第三，从7点开始，11点结束。我们假设每个任务一准备就开始，而不需要等待处理器或其他任何东西的释放。这意味着我们可以跟踪活动任务的数量：
Time #tasks
0 - 2 0
2 - 4 1
4 - 11 2
11 - 27 1我需要找到两个号码：
- 任何给定时间的最大活动任务数(本例中为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
Stack Overflow用户
发布于 2018-09-16 13:15:53
你的问题相当广泛，所以我只是给你一个挑逗的答案，希望能让你开始，尝试回答你问题的第一部分，用一个不一定是优化的解决方案。
在你的玩具输入中，你有：
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来存储结构，而不是普通数组。这样，您也可以避免动态内存分配，因为向量会自动为您处理这个问题。
https://stackoverflow.com/questions/52353906
复制相似问题
腾讯云开发者
