0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your solution doesn't seem to fit the data. There is no lecture 5 at 9:45, and no lecture 7 at 10:20. I didn't check the others. $\endgroup$ – saulspatz Apr 23 at 20:30
  • $\begingroup$ @saulspatz Ah, sorry, I messed up writing them down from the paper, there were two different orders. It’s correct now. $\endgroup$ – Nectar Apr 23 at 20:54
1
$\begingroup$

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)))
$\endgroup$
  • $\begingroup$ This is fantastic, thanks so much. Could I see the script, if you don’t mind? $\endgroup$ – Nectar Apr 24 at 21:38
  • 1
    $\begingroup$ You're welcome. I posted the script. $\endgroup$ – saulspatz Apr 24 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.