个体户可以备案网站吗,app制作工具下载,可以在哪些网站 APP做推广,网站收录没图片一解析#xff1a;
为了尽可能多的完成任务#xff0c;充分利用时间#xff0c;越早越好#xff0c;所以从项目开启的那一天起就开始做任务#xff0c;一直做到项目结束为止。
但是#xff0c;对于第i天来说#xff0c;若可执行的任务有多个#xff0c;该如何选择
为了尽可能多的完成任务充分利用时间越早越好所以从项目开启的那一天起就开始做任务一直做到项目结束为止。
但是对于第i天来说若可执行的任务有多个该如何选择根据设定这些任务都有各自的结束时间所以为了尽可能多的做任务优先选择结束时间早的任务若第i天没有任务就选择等待休息。
根据思路可写出暴力搜索的代码超时
import java.util.*;
public class Main{public static void main(String[] args){Scanner innew Scanner(System.in);int nin.nextInt();int[][] tasknew int[n][2];int minTimeInteger.MAX_VALUE,maxTimeInteger.MIN_VALUE;for(int i0;in;i){task[i][0]in.nextInt();task[i][1]in.nextInt();minTimeMath.min(minTime,task[i][0]);maxTimeMath.max(maxTime,task[i][1]);}int ans0;// 避免重复执行int[] usednew int[n];while(minTimemaxTime){int minEndInteger.MAX_VALUE,index-1;for(int i0;in;i){int[] arrtask[i];//可执行的任务中选择结束时间最早的if(used[i]0arr[0]minTimeminTimearr[1]){if(arr[1]minEnd){minEndarr[1];indexi;}}}if(index!-1){used[index]1;ans;}minTime;}System.out.println(ans);}
}
二、优化
根据暴力枚举不难得出正确答案。但是时间复杂度为O(n2)显然会超时。
1任务数组排序
第i天可执行的任务其开始时间都小于等于i若把任务数组按照开始时间进行升序排序则在寻找可执行任务时可避免全表扫描任务的开始时间超过i时停止搜索。
2扫描结果复用
对于第i天可执行的任务可收集起来供第i1天复用避免再重复扫描判断这些任务。为方便起见用队列收集第i天可执行的任务为筛选最早结束的任务队列存储任务的结束时间按小顶堆排序。
细节对于第i天收集的到可执行任务队列由于队列是复用的所以可能包含第i天之前收集的任务这些任务可能过期根据任务结束时间i判断需要清理。
3代码
import java.util.*;
public class Main{public static void main(String[] args){Scanner innew Scanner(System.in);int nin.nextInt();int[][] tasknew int[n][2];int minTimeInteger.MAX_VALUE,maxTimeInteger.MIN_VALUE;for(int i0;in;i){task[i][0]in.nextInt();task[i][1]in.nextInt();maxTimeMath.max(maxTime,task[i][1]);minTimeMath.min(minTime,task[i][0]);}Arrays.sort(task,(a,b)-a[0]-b[0]);int ans0,i0;PriorityQueueInteger queuenew PriorityQueue((a,b)-a-b);while(minTimemaxTime){while(intask[i][0]minTime){queue.add(task[i][1]);i; }//queue是可复用的所以queue中的有些任务是之前添加的可能过期需要清理while(!queue.isEmpty()queue.peek()minTime){queue.poll();}// 堆顶即被选中的任务if(!queue.isEmpty()){queue.poll();ans;}minTime;}System.out.println(ans);}
}
优化后最多访问一遍任务数组所以时间复杂度变成O(max{n,m})n为任务数m为任务最大结束时间
