Official Analysis (C++)

Solution 1 - Brute Force

Iterate over all possible times and calculate the number of buckets required at each time. We calculate the number of buckets by looping over all cows and checking which cows need to be milked.

The maximum number of buckets needed across all time is our answer.

Implementation

Time Complexity: $\mathcal{O}(N \cdot T)$, where $T$ is the maximum time in the input.

Copy
MAX_TIME = 1000

with open("blist.in") as read:
	n = int(read.readline())
	cows = [[int(i) for i in read.readline().split()] for _ in range(n)]

# The maximum number of buckets needed
max_buckets = 0

"""

Solution 2 - Sweep

Solution 1 does a lot of unnecessary work, as we don't actually have to recount the buckets for every time step. This implementation keeps track of all the changes in milking times and iterates through all the time steps at once.

Implementation

Time Complexity $\mathcal{O}(N + T)$

Copy
MAX_TIME = 1000

change = [0 for _ in range(MAX_TIME + 1)]
with open("blist.in") as read:
	n = int(read.readline().strip())
	for _ in range(n):
		start, end, amt = map(int, read.readline().strip().split())

		# at the start, we'll need some additional buckets
		change[start] += amt