c - 数据结构 : Request Counting Task

Question

我在查看此编程任务时发现了以下问题。问题陈述:专家名单开始时间和结束时间已给出。给出了任务的 end_tasks 列表。找出每个专业人员在他的时间范围内可以完成的任务数。

输入:请求:[4,2,5,3,1]，开始时间:[2,5]，结束时间:[5,6]。

输出:4 1

解释:由于 Professional_1 的时间范围为 2 到 5，他可以执行四项任务(4、2、5、3)，而 Professional_2 的时间范围为 5 到 6，他只能执行一项任务(即 5)

程序代码:

#include <stdio.h>

void count_requests(int *requests, int requests_length, int *pro_start, int pro_start_length, int *pro_end, int pro_end_length) {

    int i,j,req,start,end,task;
        for(i=0;i<pro_start_length;i++){
            start=*(pro_start+i);
            end=*(pro_end+i);
            task=0;
            for(j=0;j<requests_length;j++){
                req=*(requests+j);
                if(req>=start && req<=end){
                    task=task+1;
                }
            }
         printf("%d\n",task);
        }
}

当输入数量为 50000 时，此处嵌套的 for 循环需要超过 30 秒的运行时间。我在这里缺少什么？

Answer 1

现在您正在遍历每个工作人员的整个输入列表。相反，您可以对输入列表进行排序，然后对每个工作人员执行两次二进制搜索以确定范围内的任务索引

sortedInputs = Sort(inputs)
for(i=0;i<pro_start_length;i++){
  startIndex = BinarySearch(sortedInputs, *(pro_start+i));
  endIndex = BinarySearch(sortedInputs, *(pro_end+i));
  printf("%d\n",endIndex - startIndex)
}

当你对输入进行排序时，你有一个初始的 O(n*log(n)) 成本，但是每个任务计数的成本是 O(log(n))

---

相反，如果您有一组固定的工作人员和一个请求流(因此对请求进行排序是不切实际的)，那么您可以创建一个 Segment Tree工作人员，然后对于每个请求，您将检索可以满足该请求的工作人员集合。这具有相同的复杂性 - O(n*log(n)) 创建线段树，O(log(n)) 为每个请求查询树。