算法分析
-
1、将所有区间按左端点从小到大进行排序
-
2、从前往后枚举每个区间,在所有能覆盖start的区间中,选择右端点最大的区间,然后将start更新成右端点的最大值
证明
- 在剩下所有能覆盖start的区间中,选择右端点最大的区间,则一定会比前面的选择最优,更快达到end,所以该做法一定是最优
时间复杂度 $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 start = scan.nextInt();
int end = scan.nextInt();
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 res = 0;
boolean flag = false;
for(int i = 0;i < n;i++)
{
int j = i;
int r = Integer.MIN_VALUE;//标识是否可以完全覆盖
while(j < n && list.get(j).getFirst() <= start)
{
r = Math.max(r, list.get(j).getSecond());
j ++;
}
//若不能完全覆盖
if(r < start)
{
res = -1;
break;
}
res ++;
if(r >= end)
{
flag = true;
break;
}
start = r;
i = j - 1;
}
if(!flag) res = -1;
System.out.println(res);
}
}
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);
}
}
平时 y 总经常照顾的 java 同学就是小呆呆你吧?
建议排序写lambda表达式,简化表达