CODEWITHSUNDEEP
algorithm
user3666471
user3666471

Reputation: 945

Find interval which matches requirements

I'm trying to solve a problem where, given a 24 hour period, split up onto 15 mins each. Find all the intervals consisting of at least 1 hour long that doesn't conflict with anyone. I'm given data for N users where each user has a list of intervals they are busy for

I'm thinking if I initially maintain 1 interval of 24 hours, I can split that one interval into many small ones as I scan the intervals which are busy for the said users. Is there a better way to do it?

EDIT: Input:

[(30, 10), (70, 20)] //Busy from 7:30 AM to 10 AM, and 5:30 PM to 10:30 PM

[(0, 30), (40, 10), (90, 6)] //Busy from 12 AM to 7:30 AM, 10 AM to 12:30 PM, and 10:30 PM to 12 AM

Output:

If we search for a 1 hour period where both users are free, it should return [(50, 4), (54, 4), (58, 4), (62, 4), (66, 4)]

Upvotes: 1

Views: 74

Answers (1)

dinox0r
dinox0r

Reputation: 16059

You are given the number of blocks by day (96 blocks of 15 minutes each), create an array of 96 booleans that keeps track of the blocks that are busy (mark busy blocks as True), then iterate over the user schedules marking the busy blocks. At the end, iterate over the array again to merge all the cells with False.

For example, given the following input data:

2
30 10
70 20
3
0 30
40 10
90 6

The following code will output the blocks of at least 1 hour long that are free to both users:

#!/usr/bin/env python

# There are 96 blocks
NUM_TIME_BLOCKS = 96
# At the begining they are all free
timeBlocks = [False] * NUM_TIME_BLOCKS

with open('input.in') as times:
    for line in times:
        numBlocks = int(line)
        for n in range(0, numBlocks):
            # Get the starting time and its duration 
            (start, length) = map(int, times.next().split())

            # Mark every 15 min block as busy 
            for i in range(start, start + length):
                timeBlocks[i] = True

i = 0
while i < NUM_TIME_BLOCKS:
    if timeBlocks[i] == False:
        for j in range(i, NUM_TIME_BLOCKS):
            if timeBlocks[j]:
                break
        # We only care about blocks 1 hour long
        if j > 4:
            print '({0}, {1})'.format(i, j)
            i = j
    i += 1

You can use this as a base. Also, you have to tweak the algorithm if you want to split the answer as several blocks of one hour long. Hope it helps.

Upvotes: 2

Related Questions