AcWing 906. 区间分组-Java代码版
原题链接
简单
作者:
yqh
,
2021-01-15 13:56:42
,
所有人可见
,
阅读 370
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class 区间分组 {
/**
* 906. 区间分组
* 给定 N 个闭区间 [ai,bi] ,请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,
* 并使得组数尽可能小。
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
/**
* 创建一个类用于保存每一个区间的数据
* 依据区间的左端点进行排序
*/
class Pair implements Comparable {
int l;
int r;
public Pair(int l, int r) {
this.l = l;
this.r = r;
}
@Override
public String toString() {
return "Pair{" +
"l=" + l +
", r=" + r +
'}';
}
@Override
public int compareTo(Object o) {
if (o instanceof Pair) {
Pair p = (Pair) o;
return this.l - p.l;
}
return 0;
}
}
Pair[] range = new Pair[n];
//使用一个小根堆来维护每一组区间中最右侧的点的位置
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o1-o2);
for (int i = 0; i < n; i++) {
String[] temp = reader.readLine().split(" ");
range[i] = new Pair(Integer.parseInt(temp[0]), Integer.parseInt(temp[1]));
}
Arrays.sort(range);
/**
* 将所有区间按照左端点进行排序,再依次取出进行判断,如果当前的数(即这个集合中的最右侧的端点的值)小于
* 给定区间的右端点,说明当前的所有集合都与该区间有交集,则新建一个集合。
* 如果没有交集,则说明可以加入当前的集合中,那么删除当前的集合(即当前的数据),再将该集合的右端点插入
* 优先队列。
*/
for (int i = 0; i < n; i++) {
Pair pair = range[i];//取出一个区间
//当队列中存在数据且头元素小于当前区间的左侧端点时,删除队头元素再将当前区间的右端点插入队列
if (!heap.isEmpty() && heap.peek() < pair.l) {
heap.poll();
}
heap.add(pair.r);
}
System.out.println(heap.size());
}
}