제출 #1138410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138410		mrsmartypants	Job Scheduling (CEOI12_jobs)	Java	0 / 100	54 ms	11328 KiB

jobs

import java.io.*;
import java.util.*;

class Main {

    static int N, D, M;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        // Read input
        StringTokenizer st = new StringTokenizer(reader.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // Read the jobs
        ArrayList<Job> jobs = new ArrayList<>();
        st = new StringTokenizer(reader.readLine());
        for (int i = 0; i < M; i++) {
            int day = Integer.parseInt(st.nextToken());
            jobs.add(new Job(day, i + 1));  // Job(day, index)
        }

        // Sort the jobs based on the request day
        jobs.sort(Comparator.comparingInt(j -> j.day));

        // Binary search for minimum number of machines
        int l = 1, r = M;
        ArrayList<ArrayList<Integer>> resultSchedule = null;

        while (l < r) {
            int mid = (l + r) / 2;
            Pair<Boolean, ArrayList<ArrayList<Integer>>> feasibility = isFeasible(jobs, mid);

            if (feasibility.first) {
                r = mid;
                resultSchedule = feasibility.second;
            } else {
                l = mid + 1;
            }
        }

        // Output the result
        writer.println(l);
        for (ArrayList<Integer> daySchedule : resultSchedule) {
            for (int jobId : daySchedule) {
                writer.print(jobId + " ");
            }
            writer.println(0);
        }

        writer.close();
    }

    // Helper function to check if it's feasible with `machineCount` machines
    static Pair<Boolean, ArrayList<ArrayList<Integer>>> isFeasible(ArrayList<Job> jobs, int machineCount) {
        ArrayList<ArrayList<Integer>> schedule = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            schedule.add(new ArrayList<>());
        }

        int reqNum = 0; // Index for job requests
        for (int day = 1; day <= N; day++) {
            for (int j = 0; j < machineCount; j++) {
                // If no more jobs can be processed on this day, break
                if (reqNum == M) {
                    return new Pair<>(true, schedule);
                }

                // If the job's day is after the current day, break
                if (jobs.get(reqNum).day > day) {
                    break;
                }

                // Check if the job can be completed (if within deadline)
                if (jobs.get(reqNum).day + D >= day) {
                    schedule.get(day - 1).add(jobs.get(reqNum).id);
                    reqNum++;
                } else {
                    return new Pair<>(false, schedule);
                }
            }
        }

        return new Pair<>(false, schedule);
    }

    // Helper class to represent a job request
    static class Job {
        int day;
        int id;

        public Job(int day, int id) {
            this.day = day;
            this.id = id;
        }
    }

    // Pair class to hold a pair of values (Boolean, ArrayList)
    static class Pair<T, U> {
        T first;
        U second;

        public Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }
}

• Subtask 1: 0 / 100