|
华为面试算法题1
给定一个n*2的二维数组,表示有n个任务，一个信息是任务能够开始做的时间，,另一个信息是任务的结束期限。后者一定大于前者，且数值上都是正数，你作为单线程的人，不能并行处理任务， 但是每个任务都只需要一个单位时间完成 你需耍将所有任务的执行时间，位于开始做的时间和最后期限之间，返回你能否做到这—点。
最重要的是判断任务优先级 如何进行最优调度：
开始时间和结束时间放在一个数组里面进行排序，同时，开始时间带上自己的结束时间，结束时间带上自己的开始时间。开始时间是用来收集任务，结束时间是为了验证这个结束时间的任务有没有做完。同样的开始时间先做最先结束的任务。遍历数组。一旦存在时间差。开始时间相同就将其加入到小根堆中，此时小根堆根据这些开始时间的结束时间排序，最紧迫的任务最先做。当遇到了一个结束时间，小根堆中还存在比结束时间小的结束时间，那么就不能完成所有任务。
#include
#include
#include
#include
#include
#include
using namespace std;
struct TimePoint {
int time;//时间，开始时间或者结束时间
int end;
bool add; //if add== true,任务开始时间，else 任务结束时间。
TimePoint(int t, int e, int a) {
time = t;
end = e;
add = a;
}
};
bool canDo(vectorjobs)
{
if (jobs.size() == 0 || jobs.size() == 1)
{
return true;
}
int n = jobs.size();
vectorarr(n * 2);
//一个任务分成两个事件。
for (int i = 0; i |