區間合并：牛奶

牛奶

www.acwing.com/problem/content/description/1345/

• 本質就是區間合并問題
• 從第一次擠奶才開始計算兩個最長時間

import java.util.*;public class Main {static final int N = 5010;static Pair[] pairs = new Pair[N];static class Pair implements Comparable<Pair> {int l, r;public Pair(int l, int r) {this.l = l;this.r = r;}@Overridepublic int compareTo(Pair o) {if (this.l == o.l) {return this.r - o.r;}return this.l - o.l;}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {int l = sc.nextInt();int r = sc.nextInt();pairs[i] = new Pair(l, r);}// 排序Arrays.sort(pairs, 0, n);int left = pairs[0].l, right = pairs[0].r;int maxHasMilk = right - left, maxNoMilk = 0;for (int i = 1; i < n; i++) {if (pairs[i].l <= right) {// 連續擠奶right = Math.max(right, pairs[i].r);maxHasMilk = Math.max(maxHasMilk, right - left);} else {// 擠奶中斷left = pairs[i].l;// 現在的左端點減去上一次的右端點maxNoMilk = Math.max(maxNoMilk, left - right);right = pairs[i].r;// 注意可能一段要比多段長maxHasMilk = Math.max(maxHasMilk, right - left);}}System.out.printf("%d %d\n", maxHasMilk, maxNoMilk);}}