import java.io.*;
import java.util.*;
public class jobs {
// Maximum size for counting job requests per day.
private static final int MAX_SIZE = (int) 1e6 + 5;
// totalDays: Total number of days available.
// totalJobs: Total number of job requests.
// deadlineExtension: Extra days allowed after a job's request day.
private static int totalDays, totalJobs, deadlineExtension;
// requestCountByDay[i] stores the number of jobs that are requested on day i.
private static int[] requestCountByDay = new int[MAX_SIZE];
/**
* Checks whether the schedule is feasible using a given daily processing capacity.
*
* A deque is used to store the deadlines (day + deadlineExtension) of the pending jobs.
* For every day, jobs requested on that day add their deadline into the deque.
* Then, up to 'dailyCapacity' jobs are processed (removed from the deque).
* The schedule is feasible if, after processing all days, there are no pending jobs left.
*
* @param dailyCapacity The number of jobs that can be processed per day.
* @return true if all jobs can be processed within their deadlines, false otherwise.
*/
private static boolean isFeasible(int dailyCapacity) {
// Use a deque to track deadlines of pending jobs.
Deque<Integer> deadlineQueue = new ArrayDeque<>();
// Process each day from 1 through totalDays.
for (int day = 1; day <= totalDays; day++) {
// If there is any pending job whose deadline has passed (deadline < current day),
// the schedule is not feasible.
if (!deadlineQueue.isEmpty() && deadlineQueue.peekFirst() < day) {
return false;
}
// For all jobs requested on the current day, add their deadlines to the queue.
// Each job's deadline is its request day plus the deadlineExtension.
for (int j = 0; j < requestCountByDay[day]; j++) {
deadlineQueue.addLast(day + deadlineExtension);
}
// Process up to 'dailyCapacity' jobs for the current day.
// This simulates each machine (or processing unit) handling one job.
for (int j = 0; j < dailyCapacity; j++) {
if (deadlineQueue.isEmpty()) {
break;
}
deadlineQueue.pollFirst();
}
}
// If after all days there are no pending jobs, the schedule is feasible.
return deadlineQueue.isEmpty();
}
public static void main(String[] args) throws IOException {
// Set up input reading.
DataInputStream dis = new DataInputStream(System.in);
BufferedReader br = new BufferedReader(new InputStreamReader(dis));
// Read the first line of input: totalDays, deadlineExtension, and totalJobs.
StringTokenizer st = new StringTokenizer(br.readLine());
totalDays = Integer.parseInt(st.nextToken());
deadlineExtension = Integer.parseInt(st.nextToken());
totalJobs = Integer.parseInt(st.nextToken());
// Read the second line of input: the request day for each job.
// Reset job request counts to zero before counting.
st = new StringTokenizer(br.readLine());
Arrays.fill(requestCountByDay, 0);
for (int i = 0; i < totalJobs; i++) {
int requestDay = Integer.parseInt(st.nextToken());
requestCountByDay[requestDay]++;
}
// Binary search for the minimum daily processing capacity (machines) required.
int left = 1, right = totalJobs, optimalCapacity = 0;
while (left <= right) {
int midCapacity = (left + right) >> 1;
if (isFeasible(midCapacity)) {
// If scheduling is possible with midCapacity, try for a lower capacity.
right = midCapacity - 1;
optimalCapacity = midCapacity;
} else {
// Otherwise, increase the capacity.
left = midCapacity + 1;
}
}
// Output the found minimum daily processing capacity.
System.out.println(optimalCapacity);
// The problem output format requires printing a "0" on a new line for each day.
for (int day = 0; day < totalDays; day++) {
System.out.println(0);
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
