校门外的树 题解

思路:差分+前缀和
对于输入每组的l和r直接建立next数组差分。
next[l]++,next[r+1]--;
然后再记录前缀和，如果前缀和为0的话，说明这个地方是有一颗树的，反之没有树。

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int L = (int)in.nval;
        in.nextToken();
        int T = (int)in.nval;
        int next[] = new int[L+2];
        int l,r;
        for(int t=0;t<T;t++)
        {
        in.nextToken();
        l = (int)in.nval;
        in.nextToken();
        r = (int)in.nval;
        next[l]++;
        next[r+1]--;
        }
        int sum=0,max=0;
        for(int i=0;i<=L;i++)
        {
            sum+=next[i];
            if(sum==0)
                max++;
        }
        out.println(max);
        out.flush();
    }
                  }