AcWing 1343. 挤牛奶(Java)
原题链接
简单
作者:
Limited
,
2021-01-31 21:10:50
,
所有人可见
,
阅读 422
步骤
- 先存区间左右端点到数组
- 按左端点从小到大排序
- 遍历数组 (初始化左右界为首元素的左右端点)
- 若区间有交集(当前区间的左端点不超过已记录的右界),更新右端点
- 若区间无交集
- 连续无人时间 = 当前区间左端点 - 已记录的右界,连续有人时间 = 已记录右界 - 已记录左界
- 更新左右界为当前区间的左右端点
- 注意算时间要取较大值
- 遍历结束后,最后一个区间的连续有人时间不能漏掉
代码
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static class Interval {
public int l, r;
public Interval(int l, int r) {
this.l = l;
this.r = r;
}
}
public static void main(String[] args) {
int n = scanner.nextInt();
Interval[] f = new Interval[5010];
for (int i = 0; i < n; i++) {
f[i] = new Interval(scanner.nextInt(), scanner.nextInt());
}
Arrays.sort(f, 0, n, (o1, o2) -> {
return o1.l - o2.l;
});
int sum0 = 0, sum1 = 0;
int lnow = f[0].l, rnow = f[0].r;
for (int i = 0; i < n; i++) {
if (f[i].l <= rnow) {
rnow = Math.max(rnow, f[i].r);
} else {
sum0 = Math.max(f[i].l - rnow, sum0);
sum1 = Math.max(rnow - lnow, sum1);
lnow = f[i].l;
rnow = f[i].r;
}
}
sum1 = Math.max(rnow - lnow, sum1);
System.out.printf("%d %d\n", sum1, sum0);
}
}