제출 #1183008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183008		sur	Job Scheduling (CEOI12_jobs)	Java	5 / 100	369 ms	131072 KiB

jobs

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);
        }
    }
}

• Subtask 1: 5 / 100