The Bucket List

Solución 1 - Fuerza bruta

Iteramos sobre todos los tiempos posibles y calculamos la cantidad de baldes necesarios en cada instante. Calculamos la cantidad de baldes recorriendo todas las vacas y viendo cuáles necesitan ser ordeñadas.

El máximo de baldes necesarios a lo largo de todo el tiempo es nuestra respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(N \cdot T)$ , donde $T$ es el tiempo máximo de la entrada.

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
 
using std::cout;
using std::endl;
using std::vector;
 
const int MAX_TIME = 1000;
 
struct Cow {
	int start, end;
	int buckets;
};
 
int main() {
	std::ifstream read("blist.in");
	int n;
	read >> n;
	vector<Cow> cows(n);
	for (Cow &c : cows) { read >> c.start >> c.end >> c.buckets; }
 
	// La cantidad máxima de baldes necesarios
	int max_buckets = 0;
 
	/*
	 * Para cada instante posible, vemos cuántos baldes se necesitan en ese instante
	 * y actualizamos el máximo en consecuencia
	 */
	for (int t = 1; t <= MAX_TIME; t++) {
		int curr_buckets = 0;
		for (const Cow &c : cows) {
			if (c.start <= t && t <= c.end) { curr_buckets += c.buckets; }
		}
		max_buckets = std::max(max_buckets, curr_buckets);
	}
 
	std::ofstream("blist.out") << max_buckets << endl;
}


import java.io.*;
import java.util.*;
 
public class BList {
	static final int MAX_TIME = 1000;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blist");
		int n = io.nextInt();
		int[][] cows = new int[n][];
		for (int c = 0; c < n; c++) {
			cows[c] = new int[] {io.nextInt(), io.nextInt(), io.nextInt()};
		}
 
		// La cantidad máxima de baldes necesarios
		int maxBuckets = 0;
 
		/*
		 * Para cada instante posible, vemos cuántos baldes se necesitan en ese
		 * instante y actualizamos el máximo en consecuencia
		 */
		for (int t = 1; t <= MAX_TIME; t++) {
			int currBuckets = 0;
			for (int[] c : cows) {
				if (c[0] <= t && t <= c[1]) { currBuckets += c[2]; }
			}
			maxBuckets = Math.max(maxBuckets, currBuckets);
		}
 
		io.println(maxBuckets);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


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)]
 
# La cantidad máxima de baldes necesarios
max_buckets = 0
 
"""
Para cada instante posible, vemos cuántos baldes se necesitan en ese instante
y actualizamos el máximo en consecuencia
"""
for t in range(1, MAX_TIME + 1):
	curr_buckets = 0
	for c in cows:
		if c[0] <= t <= c[1]:
			curr_buckets += c[2]
	max_buckets = max(max_buckets, curr_buckets)
 
print(max_buckets, file=open("blist.out", "w"))

Solución 2 - Barrido

La Solución 1 hace mucho trabajo innecesario, ya que en realidad no hace falta recontar los baldes en cada paso de tiempo. Esta implementación lleva registro de todos los cambios en los horarios de ordeñe e itera por todos los pasos de tiempo de una vez.

Implementación

Complejidad temporal $\mathcal{O}(N + T)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const int MAX_TIME = 1000;
 
int main() {
	std::ifstream read("blist.in");
	int n;
	read >> n;
 
	vector<int> change(MAX_TIME + 1);
	for (int c = 0; c < n; c++) {
		int start, end;
		int amt;
		read >> start >> end >> amt;
 
		// al inicio, vamos a necesitar algunos baldes adicionales
		change[start] += amt;
		// al final, esos baldes ya no se necesitan
		change[end] -= amt;
	}
 
	int max_buckets = 0;   // la cantidad máxima de baldes necesarios
	int curr_buckets = 0;  // # de baldes que necesitamos en el tiempo de procesamiento actual
	for (int t = 0; t < MAX_TIME; t++) {
		// actualizamos la # de baldes que estamos usando
		curr_buckets += change[t];
		// actualizamos el máximo en consecuencia
		max_buckets = std::max(max_buckets, curr_buckets);
	}
 
	std::ofstream("blist.out") << max_buckets << endl;
}


import java.io.*;
import java.util.*;
 
public class BList {
	static final int MAX_TIME = 1000;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blist");
		int n = io.nextInt();
		int[] change = new int[MAX_TIME + 1];
		for (int c = 0; c < n; c++) {
			int start = io.nextInt();
			int end = io.nextInt();
			int amt = io.nextInt();
 
			// al inicio, vamos a necesitar algunos baldes adicionales
			change[start] += amt;
			// al final, esos baldes ya no se necesitan
			change[end] -= amt;
		}
 
		int maxBuckets = 0;   // máx. # de baldes que vamos a necesitar
		int currBuckets = 0;  // # de baldes que necesitamos en el tiempo de procesamiento actual
		for (int t = 0; t < MAX_TIME; t++) {
			// actualizamos la # de baldes que estamos usando
			currBuckets += change[t];
			// actualizamos el máximo en consecuencia
			maxBuckets = Math.max(maxBuckets, currBuckets);
		}
 
		io.println(maxBuckets);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


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())
 
		# al inicio, vamos a necesitar algunos baldes adicionales
		change[start] += amt
		# al final, esos baldes ya no se necesitan
		change[end] -= amt
 
max_buckets = 0  # máx. # de baldes que vamos a necesitar
curr_buckets = 0  # # de baldes que necesitamos en el tiempo de procesamiento actual
for t in range(MAX_TIME + 1):
	# actualizamos la # de baldes que estamos usando
	curr_buckets += change[t]
	# actualizamos el máximo en consecuencia
	max_buckets = max(max_buckets, curr_buckets)
 
print(max_buckets, file=open("blist.out", "w"))