summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main/JobQueue.java122
-rw-r--r--src/test/JobQueueTest.java33
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