Official Analysis (C++)

Explanation

To find the minimum possible solution, we can use binary search on the number of machines needed for finishing the jobs within the given deadline. With $M$ requests, the number of needed machines must lie in the range $[1, M]$ as in the worst case where all the requests are given on the last day, we still have $D + 1$ days to process these requests.

For each number of machines being tested, we can check its feasibility in linear time if the given job requests are already sorted in ascending order with respect to the request date. We iterate through each day $i$ from $1$ to $N$ and add requests to the schedule in the sorted order. If there is no available machine left on a certain day $i$ while there are still requests not processed, we move to next day $i+1$ and process these requests. If the day $i$ exceeds the delay limit for the current job being processed, i.e. the request date of the job added with the permitted delay is strictly less than the current day $i$, we can stop iterating as it is not possible to use the giving number of machines to process all the jobs within the deadline. Otherwise, if we have processed all job requests, the number of machines being tested is feasible, and we also found a schedule for these jobs.

Implementation

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

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

using std::vector;

int main() {
	int n, d, m;
	std::cin >> n >> d >> m;