diff options
| -rw-r--r-- | src/main/JobQueue.java | 122 | ||||
| -rw-r--r-- | src/test/JobQueueTest.java | 33 |
2 files changed, 155 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()); + } + } +} 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 |