算法分析
-
1、将所有区间按左端点从小到大排序
-
2、从前往后枚举每个区间,判断能否将其放到某个现有的组中,即是否存在当前区间的的左端点L > 任意组中右端点的最小值的组
- 如果不存在这样的组,则开新组,然后再将其放进组中
- 如果存在这样的组,则将其放在符合条件的组中,并更新当前组的右端点的值
-
3、为了不用每次选择组时都遍历所有组,可以通过小根堆来维护所有组中的尾端
证明:
-
1、按照上述存放,一定是一种合法的方案,则
Ans <= cnt
-
2、由于分了
cnt
个组,则说明一定存在cnt
个区间含有公共点,则一定至少开cnt
个组,则Ans >= cnt
综合1、2可推出Ans == cnt
时间复杂度 $O(nlogn)$
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
List<PIIs> list = new ArrayList<PIIs>();
int n = scan.nextInt();
for(int i = 0;i < n;i++)
{
int L = scan.nextInt();
int R = scan.nextInt();
list.add(new PIIs(L,R));
}
//按左端点排序
Collections.sort(list);
//通过小根堆维护每组的尾端
Queue<Integer> minheap = new PriorityQueue<Integer>();
for(PIIs item : list)
{
if(minheap.isEmpty() || minheap.peek() >= item.getFirst())
minheap.add(item.getSecond());
else
{
//更新小根堆
minheap.poll();
minheap.add(item.getSecond());
}
}
System.out.println(minheap.size());
}
}
class PIIs implements Comparable<PIIs>{
private int first;
private int second;
public int getFirst()
{
return this.first;
}
public int getSecond()
{
return this.second;
}
public PIIs(int first,int second)
{
this.first = first;
this.second = second;
}
@Override
public int compareTo(PIIs o) {
// TODO 自动生成的方法存根
return Integer.compare(first, o.first);
}
}
有个问题 就是 假设我最开始对右端点进行排序 按照最大不相交区间进行, 从头到尾进行遍历,每找到一个不相交区间就把它从vector中删除,每进行一次for循环就cnt++ , 当vector个数为空时, 就说明vector里边没有元素了, 但是wa了。。。。 为什么这个思路不对?😥
为什么要右端点的最小值呢
如果存在一个组,该组的右端点的最小值 比 当前枚举的组的左端点小,那就可以把当前枚举的组 放在 该组的后面
应该是右端点的最大值。因为如果是该组的最小值的话,即使当前区间的左端点比这个最小值要大,但是不一定比右端点的最大值大,那么还会有重叠部分的。
有个地方你可能搞混了,就是那个堆顶,存的是所有组中最小的那个右端点最大值
修改成:是否存在当前区间的的左端点L > 任意组中右端点的最小值的组,堆顶存的确实是所有组中右端点的最小值,如果当前区间左端点比其中一个右端点大,就可以把它放进该组