# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
361436 | AnythingWithJ | Job Scheduling (CEOI12_jobs) | Java | 1098 ms | 60696 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class jobs {
// 7 mins planning
static int N,D,M;
static int [] requests;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringTokenizer s = new StringTokenizer(br.readLine());
N = Integer.parseInt(s.nextToken());
D = Integer.parseInt(s.nextToken());
M = Integer.parseInt(s.nextToken());
requests = new int [M];
s = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
requests[i] = Integer.parseInt(s.nextToken());
}
Arrays.sort(requests);
int a = 1, b = M;
while (a != b) {
int mid = (a+b)/2;
if (works(mid)) b=mid;
else a = mid+1;
}
out.println(b);
out.close();
}
static boolean works (int numMachines) {
PriorityQueue<Integer> machines = new PriorityQueue<>();
for (int i = 0; i < numMachines; i++) machines.add(0);
int maxD = 0;
for (int i = 0; i < M; i++) {
int currDay = requests[i];
int nextAvalMachineDay = machines.poll()+1;
if (nextAvalMachineDay > currDay) {
maxD = Math.max(maxD,nextAvalMachineDay-currDay);
}
machines.add(Math.max(nextAvalMachineDay,currDay));
}
return maxD <= D;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |