Job Scheduling

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
 
using std::vector;
 
int main() {
	int n, d, m;
	std::cin >> n >> d >> m;
	vector<std::array<int, 2>> jobs(m);
	for (int i = 0; i < m; i++) {
		int day;
		std::cin >> day;
		jobs[i] = {day, i + 1};  // {fecha del pedido, índice[1...m]}
	}
 
	/*
	 * ordenamos los trabajos por fecha de pedido creciente
	 * para poder probarlos con isFeasible() en tiempo lineal y ver si
	 * se pueden hacer a tiempo con cierta cantidad de máquinas
	 */
	std::sort(begin(jobs), end(jobs));
	vector<vector<int>> res;
 
	/** @return el horario si es factible terminar los trabajos; si no, vacío */
	auto is_feasible = [&](int machine_count) -> vector<vector<int>> {
		vector<vector<int>> schedule(n);
		int req_num = 0;
 
		/*
		 * simulamos desde el día 1 hasta el último día n
		 * pasamos al día siguiente si se usaron todas las máquinas o
		 * no quedan pedidos en este día o antes
		 */
		for (int day = 1; day <= n; day++) {
			for (int j = 0; j < machine_count; j++) {
 
				/*
				 * si todos los trabajos de este día y anteriores ya terminaron,
				 * podemos pasar al día siguiente, aunque queden máquinas usables
				 * lo sabemos porque el vector jobs está ordenado
				 */
				if (jobs[req_num][0] > day) { break; }
				/*
				 * si la fecha actual es anterior al plazo del trabajo
				 * podemos agregar este trabajo al horario y pasar al siguiente
				 * pedido
				 */
				if (jobs[req_num][0] + d >= day) {
					schedule[day - 1].push_back(jobs[req_num++][1]);
				} else {  // en caso contrario, no es factible por el plazo
					return {};
				}
 
				/*
				 * si procesamos todos los pedidos, hallamos una
				 * solución factible
				 */
				if (req_num == m) { return schedule; }
			}
		}
 
		/*
		 * si no se pueden procesar todos los pedidos dentro de los n días dados,
		 * entonces no es factible
		 */
		return {};
	};
 
	int lo = 1;
	int hi = m;
	while (lo < hi) {
		int machine_num = (lo + hi) / 2;
 
		/*
		 * comprobamos si los trabajos terminarían dentro del plazo
		 * usando la cantidad actual de máquinas, es decir, machine_num
		 */
		vector<vector<int>> curr_result = is_feasible(machine_num);
 
		/*
		 * si es posible, ponemos la cota derecha como la cantidad
		 * de máquinas probada y guardamos el horario actual
		 */
		if (!curr_result.empty()) {
			hi = machine_num;
			res = curr_result;
		} else {
			/*
			 * en caso contrario, ponemos la cota izquierda como el número
			 * probado + 1 y volvemos a probar el siguiente machine_num
			 */
			lo = machine_num + 1;
		}
	}
 
	std::cout << lo << '\n';
	for (int i = 0; i < n; i++) {
		for (int idx : res[i]) { std::cout << idx << " "; }
		std::cout << 0 << '\n';
	}
}