AcWing 422. 区间合并-Java
原题链接
简单
作者:
zlnnjit
,
2021-02-01 23:08:26
,
所有人可见
,
阅读 413
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static Integer L;
private static Integer M;
private static int[][] arr;
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
L = scanner.nextInt();
M = scanner.nextInt();
arr = new int[M][2];
for (int i = 0; i < arr.length; i++) {
arr[i][0] = scanner.nextInt();
arr[i][1] = scanner.nextInt();
}
//区间左端点进行从小到大排序
Arrays.sort(arr, (o1, o2) -> (o1[0] - o2[0]));
int l = arr[0][0];
int r = arr[0][1];
int exist = 0;
for (int i = 1; i < arr.length; i++) {
int tmpl = arr[i][0];
int tmpr = arr[i][1];
if (tmpl > r) {
//无法合并,算出当前区间的树木个数
exist += r - l + 1;
l = tmpl;
r = tmpr;
} else {
r = Math.max(r, tmpr);
}
}
exist += r - l + 1;
//总树木:L + 1
System.out.println(L + 1 - exist);
}
}