summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'src/main')
-rw-r--r--src/main/JobQueue.java122
1 files changed, 122 insertions, 0 deletions
diff --git a/src/main/JobQueue.java b/src/main/JobQueue.java
new file mode 100644
index 0000000..21284f9
--- /dev/null
+++ b/src/main/JobQueue.java
@@ -0,0 +1,122 @@
+import java.io.BufferedOutputStream;
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStreamReader;
+import java.io.PrintWriter;
+import java.util.PriorityQueue;
+import java.util.StringTokenizer;
+
+public class JobQueue {
+ int numWorkers;
+ int[] jobs;
+
+ int[] assignedWorker;
+ long[] startTime;
+
+ private FastScanner in;
+ private PrintWriter out;
+
+ class TimeWorkerPair implements Comparable<TimeWorkerPair> {
+ long timerTally;
+ int workerID;
+
+ TimeWorkerPair(long timerTally, int workerID) {
+ this.timerTally = timerTally;
+ this.workerID = workerID;
+ }
+
+ @Override
+ public int compareTo(TimeWorkerPair that) {
+ if (this.timerTally > that.timerTally)
+ return 1;
+ if (this.timerTally == that.timerTally)
+ if (this.workerID > that.workerID)
+ return 1;
+ else
+ return 0;
+ return -1;
+ }
+ }
+
+ public static void main(String[] args) throws IOException {
+ new JobQueue().solve();
+ }
+
+ private void readData() throws IOException {
+ numWorkers = in.nextInt();
+ int m = in.nextInt();
+ jobs = new int[m];
+ for (int i = 0; i < m; ++i) {
+ jobs[i] = in.nextInt();
+ }
+ }
+
+ private void writeResponse(int[] assignedWorker, long[] startTime) {
+ for (int i = 0; i < jobs.length; ++i) {
+ out.println(assignedWorker[i] + " " + startTime[i]);
+ }
+ }
+
+ void assignJobs() {
+ // This is the naive and slow algorithm
+ assignedWorker = new int[jobs.length];
+ startTime = new long[jobs.length];
+ long[] nextFreeTime = new long[numWorkers];
+ for (int i = 0; i < jobs.length; i++) {
+ int duration = jobs[i];
+ int bestWorker = 0;
+ for (int j = 0; j < numWorkers; ++j) {
+ if (nextFreeTime[j] < nextFreeTime[bestWorker])
+ bestWorker = j;
+ }
+ assignedWorker[i] = bestWorker;
+ startTime[i] = nextFreeTime[bestWorker];
+ nextFreeTime[bestWorker] += duration;
+ }
+ }
+
+ void assignJobsImproved() {
+ assignedWorker = new int[jobs.length];
+ startTime = new long[jobs.length];
+ PriorityQueue<TimeWorkerPair> workerPq = new PriorityQueue<>();
+ for (int i = 0; i < numWorkers; i++) {
+ workerPq.add(new TimeWorkerPair(0, i));
+ }
+ for (int i = 0; i < jobs.length; i++) {
+ TimeWorkerPair l = workerPq.remove();
+ startTime[i] = l.timerTally;
+ assignedWorker[i] = l.workerID;
+ workerPq.add(new TimeWorkerPair(l.timerTally + jobs[i], l.workerID));
+ }
+ }
+
+ private void solve() throws IOException {
+ in = new FastScanner();
+ out = new PrintWriter(new BufferedOutputStream(System.out));
+ readData();
+ assignJobsImproved();
+ writeResponse(assignedWorker, startTime);
+ out.close();
+ }
+
+ static class FastScanner {
+ private BufferedReader reader;
+ private StringTokenizer tokenizer;
+
+ FastScanner() {
+ reader = new BufferedReader(new InputStreamReader(System.in));
+ tokenizer = null;
+ }
+
+ String next() throws IOException {
+ while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+ tokenizer = new StringTokenizer(reader.readLine());
+ }
+ return tokenizer.nextToken();
+ }
+
+ int nextInt() throws IOException {
+ return Integer.parseInt(next());
+ }
+ }
+}