Algorithm to find meeting time slots where all participants are available

Question

Came across this question in an interview blog. Given free-time schedule in the form (a - b) i.e., from 'a' to 'b' of n people, print all time intervals where all n participants are available. It's like a calendar application suggesting possible meeting timinings.

Example:

Person1: (4 - 16), (18 - 25)
Person2: (2 - 14), (17 - 24)
Person3: (6 -  8), (12 - 20)
Person4: (10 - 22)

Time interval when all are available: (12 - 14), (18 - 20).

Please share any known optimal algorithm to solve this problem.

I am thinking of the following solution.

• Create a currentList of intervals that contain one interval from each person. Initially currentList = [4-16, 2-14, 6-8, 10-22].

• Look for the max_start and min_end in currentList and output (max_start, min_end) if max_start < min_end; Update all intervals in currentList to have start value as min_end. Remove the interval that has min_end from currentList and add the next entry in that person's list to currentList.

• If max_start >= min_end in previous step, update all intervals in currentList to have start value as max_start. If for any interval i, end > start, replace that interval in currentList with the next interval of the corresponding person.

Based on the above idea, it will run as below for the given example:

currentList = [4-16, 2-14, 6-8, 10-22]   max_start=10 >= min_end=8

update start values to be 10 and replace 6-8 with next entry 12-20.

currentList = [10-16, 10-14, 12-20, 10-22] max_start=12 <= min_end=14

add max_start-min_end to output and update start values to 14. Output=[12-14]

currentList = [14-16, 17-24, 14-20, 14-22] max_start=17 >= min_end=16

update start values to be 17 and replace 14-16 with 18-25

currentList = [18-25, 17-24, 17-20, 17-22] max_start=18 <= min_end=20

add max_start-min_end to output and update start values to 20. Output=[12-14, 18-20]

currentList = [20-25, 2-24, - , 2-22]

Terminate now since there are no more entry from person 3.

I have not implemented the above though. I am thinking of a min-heap and max-heap to get the min and max at any point. But I am concerned about updating the start values because updating the heap may become expensive.

Answer 1

A starting point, still to optimize a bit, might be the following (code is in Python). You have the following data (the allPeople list will be clearly created dynamically):

person_1 = ["4-16","18-24"]
person_2 = ["2-14","17-24"]
person_3 = ["6-8","12-20"]
person_4 = ["10-22"]
allPeople = [person_1, person_2, person_3, person_4]

What you might do is to create a list containing all the time slots of the day (i.e. ["0-1", "1-2", "2-3", etc.] as follows:

allTimeSlots = []
for j in range(0,24):
    allTimeSlots.append(str(j) + "-" + str(j+1))

and then create a list called commonFreeSlots, which is made of all the time slots that are inside each person's free time slot collection:

commonFreeSlots = []
for j in range(0,len(allTimeSlots)):
    timeSlotOk = True
    for k in range(0,len(allPeople)):
        person_free_slots = parseSlot(allPeople[k])
        if allTimeSlots[j] not in person_free_slots:
            timeSlotOk = False
            break
    if timeSlotOk:
        commonFreeSlots.append(allTimeSlots[j])

Please note that the function parseSlot is just taking a list of strings (like "2-14","15-16") and returning a list of hourly time slots (like ["2-3","3-4","4-5" etc.] in order to make it comparable with the hourly time slot list allTimeSlots created above:

def parseSlot(list_of_slots):
    result = []
    for j in range(0,len(list_of_slots)):
        start_time = int(list_of_slots[j].split("-")[0])
        end_time = int(list_of_slots[j].split("-")[1])
        k = 0
        while (start_time + k) < end_time:
            result.append(str(start_time+k) + "-" + str(start_time+k+1))
            k += 1
    return result

If I run the above script, I get the following result:

['12-13', '13-14', '18-19', '19-20']

Of course you will have to still work a bit the output in order to aggregate the hours (and having ['12-14','18-20'] instead of the hourly version), but this should be easier I think.

The above solution should work always, however I'm not sure it's optimal, it probably exists a better one. But since you didn't share any attempt yet, I guess you'd just like some tips to get started so I hope this one helps a bit.

Answer 2

Got this today during an interview. Came up with an O(N*logN) solution. Wondering whether there is an O(N) solution available...

Overview: Join individual schedules into one list intervals --> Sort it by intervals' starting time --> Merge adjacent intervals if crossing --> Returning the availability is easy now.

import unittest


# O(N * logN) + O(2 * N) time
# O(3 * N) space

def find_available_times(schedules):
    ret = []

    intervals = [list(x) for personal in schedules for x in personal]

    intervals.sort(key=lambda x: x[0], reverse=True)  # O(N * logN)

    tmp = []

    while intervals:
        pair = intervals.pop()    
    
        if tmp and tmp[-1][1] >= pair[0]:
            tmp[-1][1] = max(pair[1], tmp[-1][1])

        else:
            tmp.append(pair)
    
    for i in range(len(tmp) - 1):
        ret.append([tmp[i][1], tmp[i + 1][0]])    

    return ret


class CalendarTests(unittest.TestCase):

    def test_find_available_times(self):
        p1_meetings = [
            ( 845,  900),
            (1230, 1300),
            (1300, 1500),
        ]

        p2_meetings = [
            ( 0,    844),
            ( 845, 1200), 
            (1515, 1546),
            (1600, 2400),
        ]

        p3_meetings = [
            ( 845, 915),
            (1235, 1245),
            (1515, 1545),
        ]

        schedules = [p1_meetings, p2_meetings, p3_meetings]
       
        availability = [[844, 845], [1200, 1230], [1500, 1515], [1546, 1600]]

        self.assertEqual(
            find_available_times(schedules), 
            availability
            )


def main():
    unittest.main()


if __name__ == '__main__':
    main()

Answer 3

I prefer to take a slightly different approach that's set based! I'll let the language elements do the heavy lift for me. As you guys have already figured out I'm making some assumptions that all meetings are on the top of the hour with an interval length of 1 hour.

def get_timeslots(i, j):
    timeslots = set()
    for x in range (i, j):
        timeslots.add((x, x + 1))
    
    return timeslots

if __name__ == "__main__":
    allTimeSlots = get_timeslots(0, 24)

    person1TimeSlots = get_timeslots(4, 16).union(get_timeslots(18, 24))
    person2TimeSlots = get_timeslots(2, 14).union(get_timeslots(17, 24))
    person3TimeSlots = get_timeslots(6,8).union(get_timeslots(12, 20))
    person4TimeSlots = get_timeslots(10, 22)

    print(allTimeSlots
        .intersection(person1TimeSlots)
        .intersection(person2TimeSlots)
        .intersection(person3TimeSlots)
        .intersection(person4TimeSlots))

Answer 4

Dmitry's solution is good enough for most scenarios, but here's another take with O(k * N) time and O(k) extra space, where N is the number of meetings, and k is the granularity of your time slots. If every meeting is known to be hourly, then k can be 24. If the meetings are held every 30 minutes, then k can be 48. k can go all the way up to 60 * 24 (your granularity is every minute in a day). You can also let k be the GCD of all times in minutes.

Overview: Make an k-sized array of booleans called A, where each index corresponds to availability in your time granularity. It begins with every slot available. Run over all meetings. Set the indexes between the start and end time of the meeting in A to False. In the end, A holds the free time slots common for everyone. The times must be in minutes for the algorithm to work.

minutesInDay = 60 * 24


def minuteToString(time):
    hour = str(int(time / 60))
    minute = str(int(time % 60))

    if len(hour) == 1:
        hour = '0' + hour
    if len(minute) == 1:
        minute = '0' + minute

    return hour + ':' + minute


def stringToMinute(time):
    hour, minute = time.split(':')
    return 60 * int(hour) + int(minute)


def availableTimeSlots(meetings, k):
    freeTime = [True] * k
    step = int(minutesInDay / k)

    for meet in meetings:
        for i in range(int(meet[0] / step), int(meet[1] / step)):
            freeTime[i] = False

    result = list()
    openInterval = False
    beg, end = 0, 0
    for i, slot in enumerate(freeTime):
        if not openInterval and slot:
            openInterval = True
            beg = i
        elif openInterval and not slot:
            openInterval = False
            end = i
            beg = minuteToString(beg * step)
            end = minuteToString(end * step)
            result.append((beg, end))

    return result


def main():
    p1 = [
        ('9:00', '10:30'),
        ('12:00', '13:00'),
        ('16:00', '18:00'),
    ]

    p2 = [
        ('10:00', '11:30'),
        ('12:30', '14:30'),
        ('14:30', '15:00'),
        ('16:00', '17:00'),
    ]

    p3 = [
        ('00:00', '8:00'),
        ('12:00', '14:00'),
        ('18:00', '24:00'),
    ]

    meetings = [
        list(map(stringToMinute, meeting)) for p in [p1, p2, p3]
        for meeting in p
    ]
    print(meetings)
    print(availableTimeSlots(meetings, 48))


if __name__ == '__main__':
    main()

Answer 5

The below is the javascript solution for the problem. Its complexity is O(n^3) but since the time is finite it can be considered n^2

function getFreeMeetingTime(allPeople) {
  // get a range of time in a day.
  // you can pass the min and max from the input if its not 0 to 24 hrs
  const allTimeSlotsInDay = getAllTimeSlots();
  let tempResult = [];
  
  for (const person of allPeople) {
    for (const time of person) {
      for (
        let i = Number(time.split('-')[0]);
        i < Number(time.split('-')[1]);
        i++
      ) {
        const val = `${i}-${i + 1}`;
        if (!tempResult.includes(val)) {
          tempResult.push(val);
        }
      }
    }
  }
  // merge the times in between. ex '4-5', '5-6' to '4-6'
  return mergeTime(
    allTimeSlotsInDay.filter((time) => !tempResult.includes(time))
  );
}

function mergeTime(timeArray) {
  const result = [];
  let i = 0;
  while (i < timeArray.length) {
    const arr = timeArray[i].split('-');
    let start = Number(arr[0]);
    let end = Number(arr[1]);
    let counter = 0;
    for (let j = i + 1; j < timeArray.length; j++) {
      const jarr = timeArray[j].split('-');
      const jstart = Number(jarr[0]);
      const jend = Number(jarr[1]);

      if (end == jstart || end >= jstart) {
        end = jend;
        counter++;
      }
    }

    i = counter === 0 ? ++i : i + counter + 1;
    result.push(`${start}-${end}`);
  }
  return result;
}

function getAllTimeSlots() {
  const result = [];
  for (let i = 0; i < 24; i = i + 1) {
    result.push(`${i}-${i + 1}`);
  }
  return result;
}

/**
 * Creating a sample data to test
 */

//sample time slots of persons where they are busy
const person_1 = ['5-6', '18-24'];
const person_2 = ['2-4', '17-24'];
const person_3 = ['6-8', '12-20'];
const person_4 = ['10-22'];

// Getting an array of time schedules where people are busy.
const allPeople = [person_1, person_2, person_3, person_4];

// get data back to result
const result = getFreeMeetingTime(allPeople);
console.log(result)

you can check the detailed code in the below link

https://www.hectane.com/blog/meeting-when-all-people-free

Answer 6

Possibly naive solutions:

1. For each participant create an integer representation of their schedule where each bit represents if they are free in that half hour / hour slot. Then do a Bitwise and of all strings.

2. Alternatively, create N tables for N participants where Col1 = TimeSlot and Col2 = Free/Not and join them all.