广联达 8.31 笔试

给定座位数 N，编号 1 ~ n，以及 m 个规则，规则规定座位编号 l 到 r 可坐 x 人

示例输入：

14 4 1 3 2 4 7 3 6 10 2 10 14 3

输出：

图解说明：

记录每一区间不可坐的位置数目，累加。如{1 3 2} 中，有一个位置不可坐，noAns += 1。

由于不知道下一区间是否会与当前区间重叠，所以不可坐位置数目还有另外的作用。

发生重叠时：

计算当前区间总共可坐的位置数

不重叠的座位数，如图中{8 9 10}
重叠座位{6 7} 以及可以坐的位置数{7}

总共 4 位。

问题来了，因为上一区间不知道下一区间会重叠，因此累加了不可坐位置数，要进行补偿。

上一区间{4 7 3}，不可坐位置数 1，并在重叠区间（即当前区间）利用了 1 个位置，那么，总不可坐位置数 - 1

import java.util.Arrays;
import java.util.Comparator;
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[][] rules = new int[m][3];

        for(int i = 0; i < m; i++) {
            rules[i][0] = sc.nextInt();
            rules[i][1] = sc.nextInt();
            rules[i][2] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(rules, new Comparator<int[]>() { 
                        @Override    public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int allSit = rules[0][1] - rules[0][0] + 1;
        int noSit = allSit - rules[0][2];
        int noAns = noSit;
        for(int i = 1; i < m; i++) {
            if(rules[i-1][1] >= rules[i][0]) {
                allSit = rules[i][1] - rules[i-1][1] + Math.min(rules[i-1][1] - rules[i][0] + 1, noSit);
                noAns -= Math.min(rules[i - 1][1] - rules[i][0] + 1, noSit);
            }else{
                allSit = rules[i][1] - rules[i][0] + 1;
            }
            noSit = allSit - rules[i][2];
            noAns += noSit;
        }
        System.out.println(noAns);
        int ans = n - noAns;
        System.out.println(ans);

    }
}