牛客练习赛34 c题 little w and Segment Coverage

链接：https://ac.nowcoder.com/acm/contest/297/C
来源：牛客网

题目描述
小w有m条线段，编号为1到m。

用这些线段覆盖数轴上的n个点，编号为1到n。

第i条线段覆盖数轴上的区间是L[i]，R[i]。

覆盖的区间可能会有重叠，而且不保证m条线段一定能覆盖所有n个点。

现在小w不小心丢失了一条线段，请问丢失哪条线段，使数轴上没被覆盖到的点的个数尽可能少，请输出丢失的线段的编号和没被覆盖到的点的个数。如果有多条线段符合要求，请输出编号最大线段的编号（编号为1到m）。

输入描述:
第一行包括两个正整数n，m(1≤n，m≤10^5)。
接下来m行，每行包括两个正整数L[i]，Ri。
输出描述:
输出一行，包括两个整数a b。
a表示丢失的线段的编号。
b表示丢失了第a条线段后，没被覆盖到的点的个数。
示例1
输入

5 3
1 3
4 5
3 4

输出

3 0

说明
若丢失第1条线段，1和2没被线段覆盖到。
若丢失第2条线段，5没被线段覆盖到。
若丢失第3条线段，所有点都被线段覆盖到了。

示例2
输入

6 2
1 2
4 5

输出

2 4

说明
若丢失第1条线段，1，2，3，6没被线段覆盖到。
若丢失第2条线段，3，4，5，6没被线段覆盖到。

这里用差分区间进行读入，储存线段覆盖情况，然后记录没有被覆盖到的地方，并找出覆盖值为1的情况。然后以此得出从 1-x 中覆盖为 1 的个数。就能得出结果啦

java AC代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] data = new int[n+2];
        int[] l = new int[m], r = new int[m];
        for (int i = 0; i < m; i++) &#123;
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
            data[l[i]]++;
            data[r[i] + 1]--;
        &#125;
        int sum = data[0];
        int oth=0;
        for (int i = 1; i <= n; i++) &#123;
            sum += data[i];
            if (sum == 1) &#123;
                data[i] = 1;
            &#125; else if (sum == 0) &#123;
                oth++;
            &#125; else &#123;
                data[i] = 0;
            &#125;
        &#125;
        for (int i = 1; i <= n; i++) &#123;
            data[i] += data[i - 1];
        &#125;
        int a = 0, b = 1000000;
        for (int i = 0; i < m; i++) &#123;
            int xi = data[r[i]] - data[l[i]-1];
            if (xi <= b) &#123;
                a = i;
                b = xi;
            &#125;
        &#125;
        System.out.println((a + 1) + " " + (b+oth));
    &#125;
&#125;