| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1182946 | sosuke | Job Scheduling (CEOI12_jobs) | Java | 0 ms | 0 KiB |
import java.io.*;
import java.util.*;
public class JobScheduling {
public static void main(String[] args) {
Kattio io = new Kattio();
int n = io.nextInt();
int d = io.nextInt();
int m = io.nextInt();
int[][] jobs = new int[m][2];
for (int i = 0; i < m; i++) {
int day = io.nextInt();
jobs[i] = new int[]{day, i + 1}; // {request date, index[1...m]}
}
/*
* we sort the jobs by the request date in ascending order
* so that we can test them using isFeasible() in linear time whether they
* can be done in given time using a certain amount of machines
*/
Arrays.sort(jobs);
List<List<Integer>> result = new ArrayList<>();
int lo = 1, hi = m;
while (lo < hi) {
int machineNum = (lo + hi) / 2;
/*
* test if the jobs would finish within the deadline
* using the current # of machines i.e., machine_num
*/
List<List<Integer>> currResult = isFeasible(n, d, m, machineNum, jobs);
/*
* if it's possible, we set the right bound as the tested
* machine number and save the current schedule
*/
if (!currResult.isEmpty()) {
hi = machineNum;
result = currResult;
} else {
/*
* otherwise, we set the left bound to be the tested number + 1
* and test the next machine_num again
*/
lo = machineNum + 1;
}
}
io.println(lo);
for (List<Integer> daySchedule : result) {
for (int idx : daySchedule) {
io.print(idx + " ");
}
io.println(0);
}
io.close();
}
/** @return true along with schedule if it feasible to finish the jobs otherwise false */
private static List<List<Integer>> isFeasible(int n, int d, int m, int machineCount, int[][] jobs) {
List<List<Integer>> schedule = new ArrayList<>();
for (int i = 0; i < n; i++) {
schedule.add(new ArrayList<>());
}
int reqNum = 0;
/*
* we simulate from day 1 until the last day n
* we move to the next day if all the machines are used or
* there is no more job requests left on or before this day
*/
for (int day = 1; day <= n; day++) {
for (int j = 0; j < machineCount; j++) {
/*
* if all jobs before and on this day are finished,
* we can go to the next day, even if there are usable machines left
* we can determine that since the vector jobs is sorted
*/
if (reqNum >= m || jobs[reqNum][0] > day) {
break;
}
/*
* if the current date is before the deadline for the job
* we can add this job to the schedule and move to the next
* job request
*/
if (jobs[reqNum][0] + d >= day) {
schedule.get(day - 1).add(jobs[reqNum++][1]);
} else { // otherwise, it is not feasible due to deadline
return Collections.emptyList();
}
/*
* if we have processed all the requests, we have found a
* feasible solution
*/
if (reqNum == m) {
return schedule;
}
}
}
/*
* if not all the requests can be processed within the given n days,
* then it is not feasible
*/
return Collections.emptyList();
}
// CodeSnip{Kattio}
static class Kattio extends PrintWriter {
private BufferedReader r;
private StringTokenizer st;
// standard input
public Kattio() { this(System.in, System.out); }
public Kattio(InputStream i, OutputStream o) {
super(o);
r = new BufferedReader(new InputStreamReader(i));
}
// USACO-style file input
public Kattio(String problemName) throws IOException {
super(problemName + ".out");
r = new BufferedReader(new FileReader(problemName + ".in"));
}
// returns null if no more input
public String next() {
try {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(r.readLine());
return st.nextToken();
} catch (Exception e) { }
return null;
}
public int nextInt() { return Integer.parseInt(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public long nextLong() { return Long.parseLong(next()); }
}
}