题解 | 校门外的树

import java.util.Scanner;
import java.util.*;

/**
* 参考deepseek：https://chat.deepseek.com/share/m17g1h95v6nn9w8hhk
*/
public class Main {
  // 方法1：使用区间合并思想
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 while 处理多个 case
        // 注意 hasNext 和 hasNextLine 的区别
        int L = in.nextInt();// 总数为L+1
        int M = in.nextInt();// 地铁施工区域数

        // 1. 按区间起点排序
        int[][] intervals = new int[M][2];
        while (in.hasNextInt()) {
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < 2; j++) {
                    // j：0,1,表示左右两个端点
                    intervals[i][j] = in.nextInt();
                }
            }
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // 2. 合并重叠区间
        List<int[]> merged = new ArrayList<>();
        int[] current = intervals[0].clone();// 第0行的两个端点
        // [0,1,2,3,4,5,6,7,8,9,10,......,L]
        // [0,1]            |
        // [0         5]    |--->合并为[0,5]
        // [  1    3]       |
        //              [6,   9]
        // merged结果:[[0,5],[6,9]]
        for (int i = 1; i < intervals.length;
                i++) { // 从第1行的两个端点开始遍历
            if (intervals[i][0] <= current[1]) { // 有重叠，合并区间
                current[1] = Math.max(current[1],
                                      intervals[i][1]); //比较两行数据右端点哪个更大，取较大者
            } else {
                merged.add(current);// 无重叠，保存当前区间，开始新区间
                current = intervals[i].clone();
            }
        }
        merged.add(current);
        // 3.计算总覆盖长度
        int totalCovered = 0;
        for (int[] interval : merged) {
            int len = interval[1] - interval[0] + 1;
            totalCovered += len;
        }

        // 4.计算剩余长度
        int totalLength = L + 1;
        int remaining = totalLength - totalCovered;
        System.out.println(remaining);
    }
}