桶列表

题目

链接：1715. 桶列表 - AcWing题库

Farmer John 正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。

他认为这最终能使得他使用数量更少的桶，然而他不清楚具体是多少，请帮助他！

Farmer John 有 N 头奶牛，方便起见编号为 1…N。

第 i 头奶牛需要从时刻 si 到时刻 ti 之间挤奶，并且挤奶过程中需要用到 bi 个桶。

多头奶牛可能在同一时刻都在挤奶；每个桶在每个时刻只能供一头奶牛使用。

也就是说，第 i 头奶牛在时刻 si 到时刻 ti 之间挤奶时，如果用到了某个桶，则该桶在这段时间不能被其他奶牛使用。

当然，这个桶在这段时间之外可以被其他奶牛所使用。

为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 si 和 ti 各不相同）。

FJ 有一个储藏室，里面有依次编号为 1、2、3、…… 的桶。

在他的挤奶策略中，当某一头奶牛（比如说，奶牛 i）开始挤奶（在时刻 si），FJ 就跑到储藏室取出编号最小的 bi 个桶分配给第 i 头奶牛用来挤奶。

请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

输入格式
输入的第一行包含 N。

以下 N 行，每行描述了一头奶牛，包含三个空格分隔的数 si,ti,bi。

其中 si 和 ti 均为 1…1000 之间的整数，bi 为 1…10 之间的整数。

输出格式
输出一个整数，为 FJ 需要的桶的数量。

数据范围
1≤N≤100

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, ans = 0;
    static int[] a = new int[1100];

    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            int s, t, b;
            s = inScanner.nextInt();
            t = inScanner.nextInt();
            b = inScanner.nextInt();
            a[s] += b;
            a[t + 1] -= b;
        }
        inScanner.close();
        int sum = 0;
        for(int i = 1; i <= 1001; i ++)
        {
            sum += a[i];
            ans = sum > ans ? sum : ans;
        }
        System.out.println(ans);
    }
}