USACO 2018 December Contest, Bronze

问题 2. 水桶清单

农场主 John 正在考虑改变他为奶牛提供水桶的方式。他认为这种改变最终能够减少水桶的总数，但他不确定到底需要多少个水桶。请帮助他解决这个问题！ 农场主 John 有 N 头奶牛（1 ≤ N ≤ 100），编号为 1 到 N。第 i 头奶牛需要在时间 si 到时间 ti 之间进行挤奶，并且需要 bi 个水桶。多个奶牛可能在同一时间段进行挤奶，如果是这样，它们不能共用同一个水桶。也就是说，分配给第 i 头奶牛的水桶，在她的挤奶期间（即从时间 si 到 ti）不能被其他奶牛使用。当然，这个水桶可以在其他时间段用于其他奶牛。为了简化工作，农场主 John 确保在任何给定的时刻，不会有多头奶牛同时开始或结束挤奶（即 si 和 ti 都是不同的）。

农场主 John 的水桶存储室中有按顺序编号的水桶，编号为 1、2、3 等等。在他目前的挤奶策略中，当某头奶牛（例如第 i 头奶牛）开始挤奶（在时间 si），农场主 John 会跑到存储室并取出编号最小的 bi 个水桶来分配给第 i 头奶牛。

请计算农场主 John 为了成功挤奶所有奶牛，至少需要多少个水桶。

输入格式 (文件 blist.in)：

• 第一行输入一个整数 N，表示奶牛的数量。
• 接下来 N 行，每行描述一头奶牛，包含三个整数 si、ti 和 bi，分别表示该奶牛的挤奶开始时间、结束时间和所需的水桶数。si 和 ti 的值都在 1 到 1000 之间，bi 的值在 1 到 10 之间。

输出格式 (文件 blist.out)：

输出一个整数，表示农场主 John 至少需要多少个水桶。

示例输入：

3
4 10 1
8 13 3
2 6 2

示例输出：

4

题目分析：

• 每次奶牛开始挤奶时，需要从存储室中取出一定数量的水桶，如果有多个奶牛在同一时段挤奶，就需要确保水桶不冲突。
• 我们可以按照奶牛的挤奶时间区间进行排序，模拟奶牛的挤奶过程。在每个时刻，检查当前需要的水桶数，并跟踪当前已分配的水桶状态。
• 目标是计算所需的最小水桶数量，保证每个时段内不会出现水桶冲突。