From 3a6cbab3d53e5b04a6ea10df7854e4f3bce4f3a3 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 21 Feb 2019 19:54:08 -0600
Subject: Parallel processing job queue done!

Fun exercise. Facing a difficult problem, always take small/concrete and
concrete steps, and you'll get there! Writing down pseudo code helped,
along with creating a subclass implementing the Comparable interface.
Good thing that I've done that before and have example to follow.
---
 src/main/JobQueue.java     | 122 +++++++++++++++++++++++++++++++++++++++++++++
 src/test/JobQueueTest.java |  33 ++++++++++++
 2 files changed, 155 insertions(+)
 create mode 100644 src/main/JobQueue.java
 create mode 100644 src/test/JobQueueTest.java

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());
+        }
+    }
+}
diff --git a/src/test/JobQueueTest.java b/src/test/JobQueueTest.java
new file mode 100644
index 0000000..e0e8a29
--- /dev/null
+++ b/src/test/JobQueueTest.java
@@ -0,0 +1,33 @@
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class JobQueueTest {
+    @Test
+    void test() {
+        int numWorkers = 2;
+        int[] jobs = {1, 2, 3, 4, 5};
+        JobQueue jobQueue = new JobQueue();
+        jobQueue.numWorkers = numWorkers;
+        jobQueue.jobs = jobs;
+        jobQueue.assignJobsImproved();
+        assertEquals(5, jobQueue.assignedWorker.length);
+        assertEquals(5, jobQueue.startTime.length);
+        assertArrayEquals(new int[]{0, 1, 0, 1, 0}, jobQueue.assignedWorker);
+        assertArrayEquals(new long[]{0, 0, 1, 2, 4}, jobQueue.startTime);
+    }
+
+    @Test
+    void test1() {
+        int numWorkers = 4;
+        int[] jobs = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
+        JobQueue jobQueue = new JobQueue();
+        jobQueue.numWorkers = numWorkers;
+        jobQueue.jobs = jobs;
+        jobQueue.assignJobsImproved();
+        assertEquals(20, jobQueue.assignedWorker.length);
+        assertEquals(20, jobQueue.startTime.length);
+        assertArrayEquals(new int[]{0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3}, jobQueue.assignedWorker);
+        assertArrayEquals(new long[]{0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4}, jobQueue.startTime);
+    }
+}
\ No newline at end of file
-- 
cgit v1.2.3