Scheduling algorithm, finding all non overlapping intervals of set length

Question

I need to implement an algorithm for my managing application that will tell me when and to which user a task can be assigned.

I implemented a brute force solution, it seems to work, but I'd like to know if there is more efficient way to do this. For sake of simplicity I've rewritten the algorithm to operate on lists of numbers(instead of db queries and such). Below i will try to explain my way of thinking.

Let's say we have 3 users that can be potentially assigned to the task.

user_a_busy = [[1,2], [2,4], [5,6]]
user_b_busy = [[4,7], [7,8]]
user_c_busy = [[0,1], [1,5]]

Each element of the list represents a period in which user is not available during the day. So User A is busy between 1 AM and 2 AM, 2 AM and 4 AM and so on. To make it possible to iterate over users and identify them i represent the above lists in form of dictionary.

users_to_check = {'A':user_a_busy, 'B':user_b_busy, 'C':user_c_busy}

Now let's say we have a task that takes 1 hour to complete and we want to check a period between midnight and 10 AM in 1 hour intervals(so tasks can start only on whole hours). Here is a representation of every period to check in form of a list.

task_intervals_to_check = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]

Here is a function that checks if two intervals overlap:

def intervals_overlap(service, busy):
    if service[1] > busy[0] and service[0] < busy[1]:
        return True
    return False

So now here is the loop that results in dictionary of available hours and users that can be assigned to the task:

result = defaultdict(list)
for interval in task_intervals_to_check:
    for user, user_busy in users_to_check.iteritems():
        overlaps = False
        for busy_period in user_busy:
            if intervals_overlap(interval, busy_period):
                overlaps = True
                break
        if not overlaps:
            result[interval[0]].append(user)

For task of length of 1 hour the result is:

{0: ['A', 'B'], 1: ['B'], 2: ['B'], 3: ['B'], 4: ['A'], 5: ['C'], 6: ['A', 'C'], 7: ['A', 'C'], 8: ['A', 'C', 'B'], 9: ['A', 'C', 'B']}

For task of length of 2 hours the result is:

{0: ['B'], 1: ['B'], 2: ['B'], 5: ['C'], 6: ['A', 'C'], 7: ['A', 'C'], 8: ['A', 'C', 'B']}

Which is an expected result. Below is the diagram which helped me to find correct results:

So now my question is, is there any way to optimise this solution? Is this an acceptable solution?

Answer 1

You can try and get rid of the outermost loop. Assuming you have the beginning and end of the period to check in ps, pe (0 and 10 in the example) and the task duration in task_duration (1 or 2 in the example). And assuming everything is in units of full hours and that the busy_intervals are sorted by time.

result = defaultdict(list)
for user, user_busy in users_to_check.iteritems():
    for l_busy_per,r_busy_per in zip([[0, ps]] + user_busy, user_busy + [[pe, 0]]):
        avail_start = l_busy_per[1]
        avail_end = r_busy_per[0]
        for hit in range(avail_start, avail_end+1-task_duration):
            result[hit].append(user)

Answer 2

I want to add a little bit on the representation of the problem. I think a representation with only the start time is both sufficient and more natural. If user a is busy from 0-1, 2-4 and 5-6 I would recommend such representation:

a_busy = (0, 2, 3, 5)

This means user a is busy for one unit of time for each time in a_busy. Also, the time slots to assign are represented more naturally that way, too.

task_times = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Then we could even use basic set theory to derive a solution for each user. Let user_busy be the set of starting times, where the user can not be assigned given a length. Furthermore let slots_to_fill be the starting times of the slots, which are desired to be filled by users, given a length. Then the difference of slots_to_fill and user_busy is the optimal assignment for the user. Here is an example for length = 2 and your user a:

user_busy = set([0, 1, 2, 3, 4, 5]) # Set where user cannot be assigned
slots_to_fill = set([0, 1, 2, 3, 4, 5, 6, 7, 8]) # Set where users shall be assigned
x = slots_to_fill - user_busy
print(x) # {6, 7, 8}

The most difficult aspect of this solution is to build the sets from your data. In this natural representation to the problem the solution is trivial and can be decomposed to be done on a per user basis:

from itertools import chain

user_busy = [[1,2], [2,4], [5,6]]
task_intervals_to_check = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]
length = 2

# Convert original data to tuples of starting times
busy_start_time = tuple(chain.from_iterable(range(i, j) for i, j in user_busy))
slots_to_fill = tuple(chain.from_iterable(range(i, j) for i, j in task_intervals_to_check))

def assign(fillslots, not_avail, length):
    return filter(lambda x: all(x+i not in not_avail for i in range(length)) and x+length-1 <= max(fillslots), fillslots)

times = assign(slots_to_fill, busy_start_time, length)
print(list(times))

This returns a list of starting times, where the user could be assigned, which are more convenient to handle than the lists. The end time can be computed by adding the length of the assignment interval to the start time.

Finally, I do not think there is much benefit in optimization regarding the run time, since this problem is rather cheap computationally. If you want to optimize the solution quality, you will first have to define an objective. E. g., this could be something like: Minimize the total number of assignments while filling all time slots. This would not increase the difficulty of the problem much though. Constraints which correlate users would make the problem significantly harder, e. g. user A and user B must not be assigned within a two hour period and user C can only be assigned if user B is also assigned.