제출 #529364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529364		ceoi_mike	Job Scheduling (CEOI12_jobs)	Java	0 / 100	134 ms	12460 KiB

jobs

import java.io.*;
import java.util.*;
class jobScheduling {
    static int N, D, M;
    static ArrayList<Job> jobs;
    static int jobIdx;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        jobs = new ArrayList<>();
        N = sc.nextInt();
        D = sc.nextInt();
        M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            int day = sc.nextInt();
            Job j = new Job(day, i+1);
            jobs.add(j);
        }
        Collections.sort(jobs, (Job j1, Job j2) -> Integer.compare (j1.day, j2.day));
        // ArrayList<ArrayList<Integer>> execSchedule = new ArrayList<>();
        // boolean result = schedule(execSchedule, 1);
        // System.out.println(result);
        ArrayList<ArrayList<Integer>> sched = new ArrayList<>();
        int result = search(1, 1000001, sched);
        System.out.println(result);
        writeSchedule(sched);   
    }


    static int search(int lo, int hi, ArrayList<ArrayList<Integer>> sched) {
        // searches for first true
        // lo will be one above known false
        // hi will be known true
        hi++;
        while (lo < hi) {
            // lo = 3 hi = 4
            int mid = lo + (hi-lo)/2;
            boolean result = schedule(sched, mid);
            if (result) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        schedule(sched, lo);
        return lo;
    }

    /*
     * execSchedule: outer array list is days, inner array list is id numbers to execute
     *    note that this function must add something to execSchedule even if an empty list
     *    because there must be an entry for the day
     * q: queue (deque) (linked list) of array list of items waiting to be execute
     * nMach: max number of machines allowed
     */
    static void execute(ArrayList<ArrayList<Integer>> execSchedule, Deque<ArrayList<Integer>> q, int nMach) {
        execSchedule.add(new ArrayList<>());
        int machLeft = nMach;
        Iterator<ArrayList<Integer>> iter = q.descendingIterator();
        while (iter.hasNext()) {
            if (machLeft == 0) break;
            ArrayList<Integer> n = iter.next();
            int qEntrySize = n.size();
            int m = Math.min(qEntrySize, machLeft);
            ArrayList<Integer> es = execSchedule.get(execSchedule.size()-1);
            for (int i = 0; i < m; i++) {
                // transfer m jobs from n (deque link) to execSchedule[-1]
                // here we are getting job from final location in n (deque link)
                int id = n.get(n.size()-1);
                n.remove(n.size()-1);
                es.add(id);
            }
            // remove from available machines
            machLeft -= m;
        }
    }

    static int computeNewJobs(ArrayList<Integer> ret, int day) {
        // ret is a list of job ids. That's all we need to know to 
        // know what we are adding to the queue. they will be associated
        // with a  certain day. they won't really be less than that
        // day because we try every day to call computer new jobs
        ret.clear();
        while (jobIdx < M && jobs.get(jobIdx).day <= day) {
            ret.add(jobs.get(jobIdx).id);
            jobIdx++;
        }
        return ret.size();
    }

    // this is top level routine. 
    static boolean schedule(ArrayList<ArrayList<Integer>> execSchedule, int nMach) {
        execSchedule.clear();
        // so we actually create the deque
        Deque<ArrayList<Integer>> deq = new LinkedList<>();
        // now we fill the deque with D+1 empty days 
        for (int i = 0; i <= D; i++ ) {
            deq.addLast(new ArrayList<Integer>());
        }
        jobIdx = 0;
        for (int day = 1; day <= N; day++) {
            // first compute new jobs that appeared today
            ArrayList<Integer> newJobIds = new ArrayList<>();
            computeNewJobs(newJobIds, day);
            // push them on the  deck
            deq.addFirst(newJobIds);
            // why at this point do we check if last entry is empty
            // well first time through known to be empty. after that
            // we call execute before we get here
            if (deq.getLast().size() > 0) {
                return false;
            }
            deq.removeLast();
            execute(execSchedule, deq, nMach);
        }
        return true;
    }

    static void writeSchedule(ArrayList<ArrayList<Integer>> sched) {
        for (ArrayList<Integer> l: sched) {
            for (int i: l) {
                System.out.print(i + " ");
            }
            System.out.println("0");
        }
    }

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

• Subtask 1: 0 / 100