Official Analysis (Java)

Video Solution

By Varun Ragunath

Explanation

Since we know the arrival times and processing times of all cows, we intuitively process them by arrival time.

To explain this, consider processing a cow that arrived later before a cow that arrived earlier. Then, at the time we process the later cow, the earlier one must already be waiting. Since both are available for questioning and processing the earlier cow never hurts, we can always question the earlier cow before the later cow and reduce waiting.

Thus, we can sort the cows by arrival time, and then process them one by one. We can track when each cow's questioning starts, since it's the later of their arrival time and when the questioning of the previous cow ended. Iterating through all the cows with this logic lets us compute the final answer.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen("cowqueue.in", "r", stdin);
	int n;

Copy
import java.io.*;
import java.util.*;

class CowQueue {
 	Code Snippet: Cow Class (Click to expand)

	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("cowqueue.in"));
		int n = Integer.parseInt(read.readLine());

Copy
import sys

sys.stdin = open("cowqueue.in")

n = int(input())

cows = []
for i in range(n):
	cows.append(list(map(int, input().split())))