算法分析
(与AC905一样)https://www.acwing.com/solution/AcWing/content/5887/
-
1、将每个区间按右端点从小到大进行排序
-
2、从前往后枚举每个区间,初始选定end值为无穷小
- 若当前区间中包含该点end,则直接跳过
- 否则,选择当前区间的右端点
-
证明:
- (1)找到
cnt
个点,满足题意情况,则最优解Ans <= cnt
- (2)找到
cnt
个点,即找到cnt
个区间,且区间从左到右依次排好,且没有相同的交集,则说明可能有区间没有被这cnt
个点覆盖过,所以最优解Ans >= cnt
- 则
Ans == cnt
,证毕
- (1)找到
时间复杂度 $O(nlogn)$
Java 代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
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);
int count = 0;
int end = Integer.MIN_VALUE;
for(PIIs item:list)
{
if(item.getFirst() > end)
{
count ++;
end = item.getSecond();
}
}
System.out.println(count);
}
}
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(second, o.second);
}
}
题干让求最大,显然第一个证明应该是
ans>=cnt
第二个证明逻辑好像有问题
第一个证明的是
Ans <= cnt
,如果看不明白可以反证证明:假设Ans > cnt
成立,又因为已经找到了cnt
个点,即cnt
个区间满足题意,又因为需要找到Ans
个两两不相交的区间,每个区间选一个点,最少需要选Ans
个点,可是按照这样子贪心找,能找到cnt
个点就能完成,因此存在Ans = cnt
的情况,因此假设错误,所以Ans > cnt
不成立,因此Ans <= cnt
第二个证明:找到
cnt
个区间,且区间从左到右依次排好,且没有相同的交集,说明这样选的区间一定是一种可行的方案,而Ans
表示的是所有可行方案的最大值,因此Ans >= cnt
一定成立你现在这样证明是对的
最优解$ans>=cnt$
证明反了吧
哪里证反了?