链接：

来源：牛客网

题目描述

小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]，R。

输出描述:

输出一行，包括两个整数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++) {
    			l[i] = sc.nextInt();			r[i] = sc.nextInt();			data[l[i]]++;			data[r[i] + 1]--;		}		int sum = data[0];		int oth=0;		for (int i = 1; i <= n; i++) {
    			sum += data[i];			if (sum == 1) {
    				data[i] = 1;			} else if (sum == 0) {
    				oth++;			} else {
    				data[i] = 0;			}		}		for (int i = 1; i <= n; i++) {
    			data[i] += data[i - 1];		}		int a = 0, b = 1000000;		for (int i = 0; i < m; i++) {
    			int xi = data[r[i]] - data[l[i]-1];			if (xi <= b) {
    				a = i;				b = xi;			}		}		System.out.println((a + 1) + " " + (b+oth));	}}