算法分析
-
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);
}
}
最爱小呆呆写的题解了QAQ
你个舔狗