Official Analysis (C++)

Explanation

Let’s focus on the chicken with the earliest time preference for helping a cow. If no cow needs to cross the road at that time, we can disregard this chicken. However, if there are cows that need to cross at that time, we have some options for assigning the chicken. Intuitively, we should assign this chicken to the cow whose crossing time window ends the earliest. This approach maximizes flexibility for assigning other chickens to cows later.

Implementation

Time Complexity: $\mathcal O(N \log N+C\log C)$

Copy
import heapq

with open("helpcross.in") as read:
	num_chickens, num_cows = [int(i) for i in read.readline().split()]

	chickens = [int(read.readline()) for _ in range(num_chickens)]

	cows = []
	for _ in range(num_cows):
		cows.append(tuple(int(i) for i in read.readline().split()))