Problem: How many 'timetables' can be created for visiting 8 different lectures without time clashes?

Question

Apologies for the poorly worded question but it really requires more explanation than can be done with one line. I have a statistics problem, or rather, a timetabling problem that I feel can be solved using mathematical methods.

Suppose you want to visit 8 different lectures in one day. Some run many times in the day, others less frequently. You want to visit all 8 in one day, leaving a gap of at least 5 minutes between lectures to travel to the next one. Each lecture lasts 30 minutes.

How many unique timetables can be created?

How many ways can all 8 lectures be arranged on a calendar for a single day such that there are no clashes, no lectures overlap and there is always 5 minutes between each lecture?

The lecture timings data is below.

Lecture 1 runs at 10:00, 12:45, 14:15.

Lecture 2 runs at 12:30, 14:45, 10:15, 13:15.

Lecture 3 runs at 11:45, 14:00.

Lecture 4 runs at 11:15, 12:00, 13:30.

Lecture 8 runs at 09:30, 11:30, 13:45, 14:45, 15:30.

Lecture 5 runs at 09:45, 10:25, 12:05, 12:55, 14:35, 15:25.

Lecture 6 runs at 11:15, 13:45.

Lecture 7 runs at 10:20, 11:20, 12:50, 15:20.

I figure possibly a very large Venn diagram could be used. I improvised a timeline-like chart on paper and manually found 1 solution, which is below.

Lecture 5 at 9:45 to 10:15

Lecture 7 at 10:20 to 10:50

Lecture 6 at 11:15 to 11:45

Lecture 4 at 12:00 to 12:30

Lecture 1 at 12:45 to 13:15

Lecture 3 at 14:00 to 14:30

Lecture 2 at 14:45 to 15:15

Lecture 8 at 15:30 to 16:00

How can I calculate if this is the only solution? Can I calculate the number of solutions? Can I visualise the data and easily pick out solutions?

I'm very interested in this problem, and I hope maybe somebody on here can assist or give suggestions on how I could solve this.

Thanks.

Answer 1

According to my calculations there are $4$ possible schedules:

['12:45', '14:45', '14:0', '12:0', '9:45', '11:15', '10:20', '15:30']
['12:45', '14:45', '14:0', '12:0', '10:25', '11:15', '15:20', '9:30']
['12:45', '14:45', '14:0', '12:0', '15:25', '11:15', '10:20', '9:30']
['12:45', '10:15', '14:0', '12:0', '14:35', '11:15', '15:20', '9:30']

I didn't take the trouble to format the output nicely, I'm afraid. The interpretation of the first schedule is:

• attend lecture 1 at 12:45
• attend lecture 2 at 14:25
• attend lecture 3 at 14:00
• and so on

I assumed that in you data, the last lecture for lecture 1 is at 14:15 rather than and 2:15 and the last lecture for lecture 2 is at 13:15.

There are so few possibilities that my script just takes the cartesian product of all possible lectures, and checks which ones are admissible.

EDIT

Here's the script as you requested, but it's very simple-minded.

from itertools import product

def format(t):
    return '%s:%s'% divmod(t,60)

lecture = 9*[None]
lecture[1] = [(10,00), (12,45), (14,15)]
lecture[2] = [(12,30), (14,45), (10,15), (13,15)]
lecture[3] = [(11,45), (14,00)]
lecture[4]= [(11,15), (12,00), (13,30)]
lecture[8] = [(9,30), (11,30), (13,45), (14,45), (15,30)]
lecture[5] =  [(9,45), (10,25), (12,5), (12,55), (14,35), (15,25)]
lecture[6] = [(11,15), (13,45)]
lecture[7] = [(10,20), (11,20), (12,50), (15,20)]

for i in range(1,9):
    for idx, s in enumerate(lecture[i]):
        lecture[i][idx] = 60*s[0]+s[1]

schedules = []
for sched in product(*lecture[1:]):
    times = sorted(sched)
    times = zip(times, times[1:])
    if all(t[1]-t[0]>=35 for t in times):
        schedules.append(sched)

for sched in schedules: 
    print(list(map(format,sched)))