算法

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
  final static int N = 10010;

  public static int merge(ArrayList<PII> segs, int length) {
    ArrayList<PII> res = new ArrayList<>();

    PII[] array = segs.toArray(new PII[0]);
    Arrays.sort(array, 0, array.length, 
      Comparator.comparing(o -> ((PII) o). first)
        .thenComparing(o -> ((PII) o).second));

    int st = Integer.MIN_VALUE, ed = Integer.MIN_VALUE;
    for (var item : array) {
      if (ed < item.first) {
        if (st != Integer.MIN_VALUE) res.add(new PII(st, ed));
        st = item.first; ed = item.second;
      } else ed = Math.max(ed, item.second);
    }

    if (st != Integer.MIN_VALUE) res.add(new PII(st, ed));

    int ret = 0;
    for (var item : res) {
        // System.out.println(item.first + " " + item.second);
      ret += item.second - item.first + 1;
    }

    return length - ret + 1;
  }

  public static void main(String[] args) throws IOException {
    ArrayList<PII> segs = new ArrayList<>();
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] line = in.readLine().split(" ");
    int l = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]);

    for (int a = 0; a < m; a++) {
      line = in.readLine().split(" ");
      int i = Integer.parseInt(line[0]), j = Integer.parseInt(line[1]);
      segs.add(new PII(i, j));
    }

    System.out.println(merge(segs, l));
  }
}

class PII {
  int first, second;

  public PII(int first, int second) {
    this.first = first;
    this.second = second;
  }
}