An efficient way to find the largest set of people and the meeting time given a set of free intervals, meeting length and max people allowed

Question

Let us say that I have a list of people and their free time intervals

    free_time = { 
                A:[(1,5)(7,9)]
                B:[(2,10)]
                C:[(1,3),(5,10)]
                D:[(1,4),(8,10)]
        }

Given the meeting length is 3 and max people allowed is 3. The output will be :-

Participants:[A,B] 
Meeting at (2,5)

Edit: Even though [A,D] is also a solution, I need to pick the people in the order given only. The program should return 1 set of participants only

Even though the max people allowed is 3. We could find only 2 people.

The program should output the earliest meeting time. The program need ton only find first max_allowed number of people that satisfy the constraint.

Is there any efficient way to do this without going through all the combination of people

Answer 1

I have a python based solution for you. Try this:

def can_attend(free_list, meet_iv):
    free_list.sort()
    for iv in free_list:
        if iv[0] <= meet_iv[0] and iv[1] >= meet_iv[1]:
            return True
    return False

free_time = {A: ...,}
persons = free_time.keys()
meeting = (2,5)
max_allowed = 3
attendees = []

for person in persons:
    if can_attend(free_time[person], meeting):
        attendees.append(person)
    if len(attendees) == max_allowed:
        break

print(attendees)

This is pretty straight forward IMO. If there is any confusion, feel free to ask in comments and I'll explain. (Variable names should help)