问题一: 安排最多的会议
会议包括开始时间和结束时间
贪心法:准备一个优先队列(或是一个按结束时间排序的数组),一个时间节点(表示上一个会议结束的时间)初始设置为0
遍历如果开始时间大于等于时间节点,则能能安排的会议数+1
public class BestArrange { public static class Program{ public int start; public int end; public Program(int start,int end){ this.start=end; this.end=end; } } public static int bestArrange(Program[] programs,int timePoint){ Arrays.sort(programs,(a,b)->a.end-b.end); int result=0; for(int i=0;i<programs.length;i++){ if(timePoint<=programs[i].start){ result++; timePoint=programs[i].end; } } return result; } }
问题二:
给定一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,
请你判断一个人是否能够参加这里面的全部会议。
示例 1:
输入:intervals = [[0,30],[5,10],[15,20]]
输出:false
示例 2:
输入:intervals = [[7,10],[2,4]]
输出:true
思路:和问题一思路一样
1、按结束位置从小到大排序
2、准备一个时间节点变量,初始值设置为0
3、遍历数组,如果会议开始时间小于等于时间节点,则说明可以参加这个会议,可以参加的会议数+1,时间节点设置为当前会议的结束时间
4、如果可以参加的会议数等于所有会议数,则返回true,否则false
class Solution { public class Meeting{ public int start; public int end; public Meeting(int s,int e){ this.start=s; this.end=e; } } public boolean canAttendMeetings(int[][] intervals) { if(intervals==null||intervals.length==0){ return true; } Meeting[] meetings=new Meeting[intervals.length]; for(int i=0;i<intervals.length;i++){ meetings[i]=new Meeting(intervals[i][0],intervals[i][1]); } Arrays.sort(meetings,(a,b)->a.end-b.end); int timepoint=0; int result=0; for(int i=0;i<meetings.length;i++){ if(meetings[i].start>=timepoint){ timepoint=meetings[i].end; result++; } } return meetings.length==result; } }