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());
+        }
+    }
+}