一些项目要占用一个会议室宣讲， 会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数组， 里面是一个个具体的项目)，
你来安排宣讲的日程， 要求会议室进行 的宣讲的场次最多。
返回这个最多的宣讲场次。
贪心：按照结束时间最早排序
public class BestArrange {
//将会议的开始时间和结束时间
public static class Meeting{
private int startTime;
private int endTime;
public Meeting(int startTime, int endTime){
this.startTime = startTime;
this.endTime = endTime;
}
}
//小根堆的比较器
public static class MinheapComparator implements Comparator{
@Override
public int compare(Meeting o1, Meeting o2) {
return o1.endTime - o2.endTime;
}
}
/**
* 可以利用按照结束时间排序的小根堆来完成，会议开始时间小于当前会议结束时间的都要忽略掉
* @param start
* @param end
* @param initStart
* @return
*/
public static int bestArrangeByHeap(int[] start, int[] end, int initStart){
if(start.length == 0 || end.length == 0 || (start.length != end.length)) return 0;
int res = 0;
//利用优先队列和小根堆比较器构建小根堆
//按照结束时间进行排序
PriorityQueue meetings = new PriorityQueue<>(new MinheapComparator());
for(int i = 0; i < start.length; i++){
meetings.add(new Meeting(start[i], end[i]));
}
while(meetings.size() > 0){
Meeting meeting = meetings.poll();
//如果小根堆中会议的开始时间大于当前会议的开始时间，
// 那么这些会议可以选入
//同时当前时间修改为选入会议的结束时间
if(meeting.startTime >= initStart){
res++;
initStart = meeting.endTime;
}
}
return res;
}
/**
* 还可以利用按照结束时间排序的数组来完成，
* 利用Arrays工具类的sort，其中传入比较器即可
* 会议开始时间小于当前会议结束时间的都要忽略掉
* @param start
* @param end
* @param initStart
* @return
*/
public static int bestArrangeByArray(int[] start, int[] end, int initStart){
if(start.length == 0 || end.length == 0 || (start.length != end.length)) return 0;
int res = 0;
Meeting[] meetings = new Meeting[start.length];
for(int i = 0; i < start.length; i++){
meetings[i] = new Meeting(start[i], end[i]);
}
//利用结束时间从小到大排序
Arrays.sort(meetings, new MinheapComparator());
for(int i = 0; i < meetings.length; i++){
if(meetings[i].startTime >= initStart){
res++;
initStart = meetings[i].endTime;
}
}
return res;
}
}
