题目

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入描述:

第一行有两个整数：L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述:

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
输入

500 3
150 300
100 200
470 471

输出

298

备注:

对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。

思路

有区间的交集切l<=1e4 m<=100 ,暴力一遍也是1e6 所以没啥问题
初始化 1e4+1的数组(换布尔值数据类型也行)记录树是否存在（初始化0 存在）。然后遍历每个区间 把区间内的树的标记都改为-1 （砍掉了）
然后在变量0~L 中的0的个数。

dai'ma

 public static void main(String[] args) {
        //暴力O(2^6)
        int[] tree = new int[(int) 1e4 + 1];
        Scanner cin = new Scanner(System.in);
        int l = cin.nextInt();
        int t = cin.nextInt();
        for (int i = 0; i < t; i++) {
            int start = cin.nextInt();
            int end = cin.nextInt();
            while (start != end + 1)
                tree[start++] = -1;
        }
        int count = 0;
        for (int i = 0; i <= l; i++)
            if (tree[i] == 0) count++;
        System.out.println(count);
    }

进阶 区间合并问题

数据范围增大
遇到java pair排序问题... 正在尝试搞定
java中的pair排序还得自己再写一下 他是javafx.util包下的
关于自定义类的sort折腾挺久的，一直报空指针错误，原来是初始化数字 有些数据是用不到 未定义的，所以会报错
sort限定fromIndex和toIndex即可，

package NowCoder.普及组_模拟1;

import java.util.Arrays;

import java.util.Scanner;

import static java.lang.Math.max;

public class _NOIP2005校门外的树 {
    static class MyPair<K, V> implements Comparable<MyPair> {
        Integer x;
        Integer y;

        public void setX(Integer x) {
            this.x = x;
        }

        public void setY(Integer y) {
            this.y = y;
        }

        MyPair() {
        }

        MyPair(Integer x, Integer y) {
            setX(x);
            setY(y);
        }

        /**
         * 调用Comparable接口 实现compareTo方法 便于直接sort
         * 自定义类sort规则
         *
         * @param o
         * @return
         */
        @Override
        public int compareTo(MyPair o) {
            return this.x - o.x == 0 ? this.y - o.y : this.x - o.x;

        }
    }

    public static void main(String[] args) {
        MyPair[] seg = new MyPair[110];
        Scanner cin = new Scanner(System.in);
        int l = cin.nextInt();
        int n = cin.nextInt();
        int a, b;
        for (int i = 0; i < n; i++) {
            a = cin.nextInt();
            b = cin.nextInt();
            seg[i] = new MyPair(a, b);
        }
//        Arrays.sort(seg,0,n);//使用类的比较器
        Arrays.sort(seg, 0, n, (o1, o2) -> {//自建比较器 lambda
            return o1.x - o2.x == 0 ? o1.y - o2.y : o1.x - o2.x;
        });
        //比较繁杂的比较 
//        Arrays.sort(seg, 0, n, (o1, o2) -> {
//            if (o1.x.compareTo(o2.x) == 0) {
//                if (o1.y == o2.y) return 0;
//                else if (o1.y > o2.y) return 1;
//                else return -1;
//            } else if (o1.x.compareTo(o2.x) > 0) return 1;
//            else if (o1.x.compareTo(o2.x) < 0) return -1;
//            else return 0;
//        });
        int start = seg[0].x, end = seg[0].y;
        int sum = 0;
        for (int i = 1; i < n; i++) {//判断交集
            if (seg[i].x > end) {//起点大于终点 无交集
                sum += end - start + 1;
                start = seg[i].x;//更新维护区间
                end = seg[i].y;
            } else {//当前区间和维护 有交集
                //起点一定小于终点，因为已经排序
                end = max(end, seg[i].y);
            }
        }
        sum += end - start + 1;//最后一个区间
        System.out.println(l + 1 - sum);//总长度减去被砍掉的

    }
}