P5117 [USACO18DEC] The Bucket List B

Farmer John is considering changing the way he assigns milk buckets when milking his cows. He believes this might let him use fewer buckets overall, but he does not know how many. Please help him. Farmer John has $N$ cows ($1\le N\le 100$), numbered $1\dots N$ for convenience. Cow $i$ needs to be milked from time $s_i$ to time $t_i$, and during milking it requires $b_i$ buckets. Therefore, multiple cows may be milking at the same time; if so, they cannot share the same buckets. In other words, a bucket used for cow $i$ cannot be used by any other cow that is being milked during the time interval from $s_i$ to $t_i$. Of course, that bucket can be used by other cows outside this time period. To simplify his work, FJ guarantees that at any moment, at most one cow starts or ends milking (that is, all $s_i$ and $t_i$ are pairwise distinct). FJ has a storage room with buckets numbered $1$, $2$, $3$, $\dots$ in order. Under his milking strategy, when a cow (say, cow $i$) starts milking (at time $s_i$), FJ goes to the storage room and takes the smallest-numbered $b_i$ buckets to assign to cow $i$ for milking. Compute how many buckets FJ needs to store so that he can successfully milk all cows.

The first line contains $N$. The next $N$ lines each describe one cow, containing three space-separated numbers $s_i$, $t_i$, and $b_i$. Here $s_i$ and $t_i$ are integers between $1\dots 1000$, and $b_i$ is an integer between $1\dots 10$.

Output one integer: the number of buckets FJ needs.

In this example, FJ needs $4$ buckets. He uses buckets $1$ and $2$ to milk cow $3$ (starting at time $2$). He uses bucket $3$ to milk cow $1$ (starting at time $4$). When cow $2$ starts milking at time $8$, buckets $1$ and $2$ can be reused, but bucket $3$ cannot, so he will use buckets $1$, $2$, and $4$. Translated by ChatGPT 5