# Daily Coding Problem: Problem #10

Here I am with another problem!

# Problem

Implement a job scheduler which takes in a function `f` and an integer `n`, and calls `f` after `n` milliseconds.

# Solution1: Direct implementation

The straightforward approach will be to write a function that takes a function and an integer as arguments, that waits for n milliseconds and then calls the function. Lets implement it then!

`import timedef scheduler(f, n):    time.sleep(n)    f()`

We may think that the above solution is the best, but its not!. We have consider the real world scenarios. The above methods runs sequentially, also what if we want to schedule functions that take arguments. Lets list them down.

1. Multiple functions must be scheduled
2. Function that take argument must be executed

Now to handle multiple functions, we need to think of multi-threading.

# Solution 2: Multi-threading with list

`from time import sleep, timeclass Scheduler:    def __init__(self):        self.functions = []        thread = threading.Thread(target=self._poll)        thread.start()    def _poll(self):        while True:            now = time() * 1000            if len(self.functions) > 0:                due, func, args, kwargs = self.functions                if now > due:                    func(*args, **kwargs)                self.functions = [(due, func, args, kwargs) for due, func, args, kwargs in self.functions if due < now]            sleep(0.01)    def schedule(self, func, n, *args, **kwargs):        heapq.heappush(self.functions, (n + time() * 1000, func, args, kwargs))`

Time Complexity: O(n)

Space Complexity: O(n)

We maintain a list of functions with its schedule time and arguments as a four value tuple. We run a loop to check if the current time is greater than any of the scheduled function’s time, if so we take that function and execute. The above solution may look optimal, but its not. It can still be optimized. Since the functions from the list are selected based on it scheduled time, we can maintain a heap. Min-heap guarantees that the first element is always the smallest. So when we remove that function, the time taken will be `O(log(n)) `and not `O(n)` as in the above solution.

# Solution 3: Multi-threading with min-heap

`import heapqimport threadingfrom time import sleep, timeclass Scheduler:    def __init__(self):        self.functions = []        heapq.heapify(self.functions)        thread = threading.Thread(target=self._poll)        thread.start()    def _poll(self):        while True:            now = time() * 1000            if len(self.functions) > 0:                due, func, args, kwargs = self.functions                if now > due:                    func(*args, **kwargs)                    heapq.heappop(self.functions)            sleep(0.01)    def schedule(self, func, n, *args, **kwargs):        heapq.heappush(self.functions, (n + time() * 1000, func, args, kwargs))`

Time Complexity: O(log(n))

Space Complexity: O(n)

I hope you guys enjoyed this post.

If you find it helpful, please share and claps are much appreciated! 😄