【问题描述】
给定一组报告，其中的每个报告设置了一个开始时间si和结束时间fi。设计与实现一个算法，对这组报告分配最少数量的教室，使得这些报告能无冲突的举行。
package org.xiu68.exp.exp8; import java.util.ArrayList;
import java.util.Comparator; public class Exp8_1 { public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Report> reports=new ArrayList<>();
reports.add(new Report(7,10));
reports.add(new Report(8,11));
reports.add(new Report(9,13));
reports.add(new Report(12,14));
reports.add(new Report(13,15));
intervalPartition(reports);
} public static void intervalPartition(ArrayList<Report> reports){
reports.sort(new comp()); //按开始时间对报告进行排序 //不使用优先队列
//ArrayList<Integer> classrooms=new ArrayList<>();
//classrooms.get(i)表示第i间教室的报告的结束时间
//classrooms.add(reports.get(0).endTime); //使用优先队列
PriorityQueue<ClassRoom> classrooms=new PriorityQueue<>();
//首先为第1份报告分配教室
classrooms.add(new ClassRoom(reports.get(0).endTime)); for(int i=1;i<reports.size();i++){
//不使用优先队列
/*boolean flag=false; //是否找到教室
for(int j=0;j<classrooms.size();j++){
if(reports.get(i).startTime>=classrooms.get(j)){ //找到教室
classrooms.set(j, reports.get(i).endTime);
flag=true;
break;
}
}
if(flag==false){ //找不到教室，另分配一间教室
classrooms.add(reports.get(i).endTime);
}*/ //使用优先队列
if(reports.get(i).startTime>=classrooms.getMin().endTime){ //找到教室
//教室来了新报告后需要调整使用教室的结束时间
classrooms.setFirstElement(new ClassRoom(reports.get(i).endTime));
}else{
classrooms.add(new ClassRoom(reports.get(i).endTime)); //找不到教室,新开辟一间教室
} }
System.out.println("最少需要 "+classrooms.size()+" 间教室");
} } class Report{
public int startTime; //开始时间
public int endTime; //结束时间 public Report(int startTime, int endTime) {
super();
this.startTime = startTime;
this.endTime = endTime;
}
} class ClassRoom implements Comparable<ClassRoom>{
public int endTime;
public ClassRoom(int endTime){
this.endTime=endTime;
}
@Override
public int compareTo(ClassRoom o) {
// TODO Auto-generated method stub
if(endTime>o.endTime)
return 1;
else
return -1;
}
}
class comp implements Comparator<Report>{
@Override
//按开始时间排序报告的比较方法
public int compare(Report r1, Report r2) {
// TODO Auto-generated method stub
if(r1.startTime>r2.startTime)
return 1;
else
return -1;
}
}
package org.xiu68.exp.exp8; import java.util.Comparator;
import java.util.NoSuchElementException; public class PriorityQueue<E extends Comparable<E>> {
private E[] heap;
private int size;
private Comparator<E> comp; @SuppressWarnings("unchecked")
public PriorityQueue(){
heap=(E[])new Comparable[5];
}
public PriorityQueue(Comparator<E> comp){
this();
this.comp=comp;
} @SuppressWarnings("unused")
private int compare(E e1,E e2){
if(comp==null)
return e1.compareTo(e2);
else
return comp.compare(e1, e2);
} @SuppressWarnings("unchecked")
public void add(E element){
//如果添加元素后数组已满，则先扩容再加入
if(++size==heap.length){
E[] e=(E[])new Comparable[heap.length*2];
System.arraycopy(heap, 0, e, 0, size);
heap=e;
}
heap[size-1]=element;
adjust();
} //设置堆顶元素，需要从堆顶开始调整堆
public void setFirstElement(E element){
if(size<=0){
throw new NoSuchElementException();
}
heap[0]=element;
adjustFromIndex(0);
}
public void adjustFromIndex(int i){
//由于从序号为0开始存储，需要加这段
if(i==0 && size>1){
int j;
if(size>2){ //大于等于3个元素
j=(compare(heap[i+1],heap[i+2])>0?i+1:i+2); //j为左右孩子的最小者的下标
}else{ //只有两个元素
j=i+1;
}
if(compare(heap[i],heap[j])>0){ //父结点大于子结点,交换值
E temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
}
adjustFromIndex(j);
} int parent=i;
int child=2*i;
while(child<=size-1){
//child<size-1表示parent左右孩子都存在
//child存放左右孩子最大者数组下标
if(child<size-1 && compare(heap[child],heap[child+1])>0){
child+=1;
}
if(compare(heap[parent],heap[child])<=0){ //父结点大于子结点，停止调整
break;
}else{
E temp=heap[parent];
heap[parent]=heap[child];
heap[child]=temp;
parent=child;
child=2*parent;
}
}
}
//从新加入元素开始调整堆
public void adjust(){
int newElement=size-1;
int parentElement;
while(newElement>0){ //还没有调整到根结点
parentElement=newElement/2; //根结点为newElement/2向下取整 //如果父结点小于等于子结点则不需要调整
if(compare(heap[parentElement],heap[newElement])<=0){
break;
}
//交换父结点与子结点的值
E temp=heap[parentElement];
heap[parentElement]=heap[newElement];
heap[newElement]=temp;
newElement=parentElement;
}
}
//获取最小元素
public E getMin(){
if(size==0){
throw new NoSuchElementException();
}
return heap[0];
}
//返回队列大小
public int size(){
return size;
}
}