summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--sources/job_queue.py47
-rw-r--r--tests/job_queueTest.py28
2 files changed, 75 insertions, 0 deletions
diff --git a/sources/job_queue.py b/sources/job_queue.py
new file mode 100644
index 0000000..8928d4a
--- /dev/null
+++ b/sources/job_queue.py
@@ -0,0 +1,47 @@
+# python3
+
+from heapq import heappush, heappop
+from collections import namedtuple
+
+AssignedJob = namedtuple("AssignedJob", ["worker", "started_at"])
+
+
+def assign_jobs(n_workers, jobs):
+ # Naive algorithm
+ result = []
+ next_free_time = [0] * n_workers
+ for job in jobs:
+ next_worker = min(range(n_workers), key=lambda w: next_free_time[w])
+ result.append(AssignedJob(next_worker, next_free_time[next_worker]))
+ next_free_time[next_worker] += job
+
+ return result
+
+
+def assign_jobs_improved(n_workers, jobs):
+ result = []
+ worker_priority_q = []
+ for i in range(n_workers):
+ heappush(worker_priority_q, (0, i))
+
+ for j in range(len(jobs)):
+ pair = heappop(worker_priority_q)
+ result.append(AssignedJob(pair[1], pair[0]))
+ heappush(worker_priority_q, (pair[0] + jobs[j], pair[1]))
+
+ return result
+
+
+def main():
+ n_workers, n_jobs = map(int, input().split())
+ jobs = list(map(int, input().split()))
+ assert len(jobs) == n_jobs
+
+ assigned_jobs = assign_jobs_improved(n_workers, jobs)
+
+ for job in assigned_jobs:
+ print(job.worker, job.started_at)
+
+
+if __name__ == "__main__":
+ main()
diff --git a/tests/job_queueTest.py b/tests/job_queueTest.py
new file mode 100644
index 0000000..ac95c35
--- /dev/null
+++ b/tests/job_queueTest.py
@@ -0,0 +1,28 @@
+import unittest
+
+from collections import namedtuple
+
+AssignedJob = namedtuple("AssignedJob", ["worker", "started_at"])
+
+from sources.job_queue import assign_jobs, assign_jobs_improved
+
+
+class MyTestCase(unittest.TestCase):
+ def test(self):
+ num_workers = 2
+ jobs = [1, 2, 3, 4, 5]
+ result = [AssignedJob(0, 0), AssignedJob(1, 0), AssignedJob(0, 1), AssignedJob(1, 2), AssignedJob(0, 4)]
+ self.assertListEqual(result, assign_jobs_improved(num_workers, jobs))
+
+ def test1(self):
+ num_workers = 4
+ jobs = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
+ result = [AssignedJob(0, 0), AssignedJob(1, 0), AssignedJob(2, 0), AssignedJob(3, 0), AssignedJob(0, 1),
+ AssignedJob(1, 1), AssignedJob(2, 1), AssignedJob(3, 1), AssignedJob(0, 2), AssignedJob(1, 2),
+ AssignedJob(2, 2), AssignedJob(3, 2), AssignedJob(0, 3), AssignedJob(1, 3), AssignedJob(2, 3),
+ AssignedJob(3, 3), AssignedJob(0, 4), AssignedJob(1, 4), AssignedJob(2, 4), AssignedJob(3, 4)]
+ self.assertListEqual(result, assign_jobs_improved(num_workers, jobs))
+
+
+if __name__ == '__main__':
+ unittest.main()