AcWing 907. 区间覆盖--Java写法
原题链接
简单
作者:
宇小苏
,
2021-04-29 22:07:00
,
所有人可见
,
阅读 364
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* @author: CyS2020
* @date: 2021/4/29
* 描述:区间覆盖
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
String line = input.readLine();
int[] arr = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
int st = arr[0];
int ed = arr[1];
line = input.readLine();
int N = Integer.parseInt(line);
List<Pair> intervals = new ArrayList<>();
while ((line = input.readLine()) != null) {
arr = Arrays.stream(line.split(" ")).mapToInt(Integer::parseInt).toArray();
intervals.add(new Pair(arr[0], arr[1]));
}
Collections.sort(intervals);
int cur = Integer.MIN_VALUE;
int res = 0;
int i = 0;
while(cur < ed){
for(; i < intervals.size(); i++){
Pair pair = intervals.get(i);
if(pair.left <= st){
cur = Math.max(cur, pair.right);
}else {
break;
}
}
if(cur == st){
res = -1;
break;
}
st = cur;
res++;
}
System.out.println(res);
}
public static class Pair implements Comparable<Pair> {
int left;
int right;
public Pair(int left, int right) {
this.left = left;
this.right = right;
}
@Override
public int compareTo(Pair pair) {
return this.left - pair.left;
}
}
}