AcWing 803. 区间合并-JAVA
原题链接
简单
作者:
Astarion
,
2021-03-27 09:56:18
,
所有人可见
,
阅读 347
import java.util.Arrays;
import java.io.*;
class Main {
static InputStreamReader isr = new InputStreamReader(System.in);
static BufferedReader in = new BufferedReader(isr);
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static class Range implements Comparable<Range> {
int l, r;
public Range(int l, int r) {
this.l = l;
this.r = r;
}
@Override
public int compareTo(Range o) {
return this.l - o.l;
}
}
static int N = 100010;
static int n, l, r;
static Range[ ] ranges = new Range[N];
public static void main(String[] args) throws IOException {
n = Integer.parseInt(in.readLine());
for (int i = 0; i < n; i++) {
String[] strs = in.readLine().split(" ");
int l = Integer.parseInt(strs[0]);
int r = Integer.parseInt(strs[1]);
ranges[i] = new Range(l, r);
}
Arrays.sort(ranges, 0, n);
//总区间个数,当前区间的最右边界
int cnt = 0, cur = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (i == 0 || ranges[i].l > cur) cnt++;
cur = Math.max(cur, ranges[i].r);
}
out.write(cnt+"");
in.close();
isr.close();
out.flush();
out.close();
osw.close();
}
}