AcWing 111. 畜栏预定——Java
原题链接
简单
作者:
hutFire
,
2021-06-07 18:46:42
,
所有人可见
,
阅读 181
package basic_贪心;
import java.util.*;
public class _111畜栏预定 {
public static Scanner ip = new Scanner(System.in);
private static class EatGrass implements Comparable<EatGrass>{
int st;
int ed;
int index;
public EatGrass(int st,int ed,int index){
this.st = st;
this.ed = ed;
this.index = index;
}
@Override
public int compareTo(EatGrass o) {
if (this.st > o.st){
return 1;
}else if (this.st < o.st){
return -1;
}else {
return 0;
}
}
}
public static void getMinInterval(int N){
ArrayList<EatGrass> eatGrasses = new ArrayList<>();
int[] ans = new int[N];
for (int i = 0; i < N; i++) {
eatGrasses.add(new EatGrass(ip.nextInt(),ip.nextInt(),i));
}
Collections.sort(eatGrasses);
// 存放的是该组的最大值和组编号
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
for (int i = 0; i < N; i++) {
EatGrass e = eatGrasses.get(i);
if (heap.isEmpty() || heap.peek()[0] >= e.st){
//空的开新的组,或者当前的左端点比堆的最小还小开新的组
heap.offer(new int[]{e.ed,heap.size() + 1});
ans[e.index] = heap.size();
}else {
//否则是可以放到一个组中去的
//并且维护那个组的Max_r
int[] group = heap.poll(); //所以要把原来那个组里的poll掉
group[0] = e.ed;
heap.offer(group);
ans[e.index] = group[1];
}
}
System.out.println(heap.size());
for (int i = 0; i < N; i++) {
System.out.println(ans[i]);
}
}
public static void main(String[] args) {
int N = ip.nextInt();
getMinInterval(N);
}
}