Algorithm to find best possible time slot for group of participants

Question

What algorithm would you recommend i use to solve the following problem?

I want to solve the problem of finding the best possible time slot which suits all (or nearly all) participants based on their calendar availability.

I'm using Java and want to be able schedule a meeting for these participants. I have the participants availability data for the day broken into half hour segments. I want to find a time when all these participants are available.

The availability problem looks like this

|Participant   | 09:00 | 09:30 | 10:00     | 10:30 | 11:00 | 11:30 |
|Person 1      | Free  | Busy  | **Free**  | Free  | Busy  | Free  | 
|Person 2      | Free  | Busy  | **Free**  | Free  | Busy  | Busy  | 
|Person 3      | Free  | Busy  | **Free**  | Free  | Busy  | Busy  | 
|Person 4      | Free  | Busy  | **Free**  | Free  | Busy  | Busy  | 
|Person 5      | Free  | Busy  | **Free**  | Free  | Busy  | Free  |

I want to pick the time slot which suits everyone. Ideally i would like the algorithm to pick atleast one option. I can then apply constraints to the chosen time to find the optimal.

Answer 1

The availability schedule can be converted into an array of bits, where Free would be 1 and Busy would be 0. I specified an example below to serve as a guide:

|Participant | 09:00 | 09:30 | 10:00 | 10:30 | 11:00 | 11:30 |
|Person 1    | Free  | Busy  | Free  | Free  | Busy  | Free  |

The bit array for Person 1 would look like: 1 | 0 | 1 | 1 | 0 | 1

Since you are setting the periods in increments of 30 minutes, your bit array would not exceed a size of 48 for a 24-hour time range. In Java, a long data type would be enough to hold the value of this bit array. Convert each of the participant's available timeslot into a bit array. Then, apply the bitwise operator AND to the bit array representation of the available schedule of each participant. The resulting bit array would be the common Free time of all participants.

Answer 2

Arrange a DataStructure something like this.

Map

Where the keys could range practically from Day 1 to Day N. I have assumed the next 30 days and so the keys would range from Day1 to Day30.

Assume 10 Persons are required to book a meeting. And every one should be free on that slot for the meeting to be booked.

I have assumed 30 minute slots in a 8 hr work day. So there will be 16 slots in a day.

So for Day1-> You will be holding 10 Person's availability as a 10 by 16 2 dimensional int array/matrix. Each cell will either hold 0 or 1. 0 to indicate the person is not available and 1 to indicate he is available.

The key is to do an AND of each Person/Slot in pairs iteratively. (Person1 availability on slot 0) & (Person2 availability on slot 0). If it is 0 break the loop immediately because we cannot find a match for this slot. An exact match for a slot on a particular day is arrived at if the repeated ANDs yield 1 for a day/slot combo. I have attached my code below. package com.ramesh.tests;

    import java.util.Map;
    import java.util.Random;
    import java.util.TreeMap;

    public class CalendarFinder {

        public static void main(String[] args) {
            int n=10 ;// no. of persons
            int m=30 ;//no.of days
            Map<String,int[][]> personCalendar = preparePersonCalendars(n,m);
            printPersonCalendar(personCalendar);
            Map<String,int[][]> testData = prepareTestData(n,m);
            printPersonCalendar(testData);
            meetingSlotFinder(testData);
            meetingSlotFinder(personCalendar);
        }

        private static Map<String,int[][]> preparePersonCalendars(int n, int m) {
            Random rnd = new Random();
            Map<String,int[][]> personCalendar = new TreeMap<String,int[][]>();
            for(int i=0; i<m; i++) { //iterate over days
                int[][] daysSlots = new int[n][16];
                for(int j=0;j<n;j++) { //iterate over persons
                    for(int slot=0;slot<16;slot++) { 
                        daysSlots[j][slot] = rnd.nextInt(2);
                    }
                }
                personCalendar.put(i<9 ? "Day_0"+(i+1) : "Day_"+(i+1), daysSlots);
            }
            return personCalendar;
        }

        private static Map<String,int[][]> prepareTestData(int n, int m) {
            Map<String,int[][]> testData = new TreeMap<String,int[][]>();
            for(int i=0; i<m; i++) { //iterate over days
                int[][] daysSlots = new int[n][16];
                for(int j=0;j<n;j++) { //iterate over persons
                    for(int slot=0;slot<16;slot++) { 
                        daysSlots[j][slot] = i%5==0 && slot%6==0 ? 1 : 0;
                    }
                }
                testData.put(i<9 ? "Day_0"+(i+1) : "Day_"+(i+1), daysSlots);
            }
            return testData;
        }

        private static void printPersonCalendar(Map<String,int[][]> personCalendar) {
            for(Map.Entry<String, int[][]> calendar: personCalendar.entrySet()) {
                System.out.println("Printing Calendar availability for : " + calendar.getKey());
                int[][] pCalArray = calendar.getValue();
                for(int i=0; i<pCalArray.length; i++) {
                    System.out.println("Person : " + (i+1));
                    for(int j=0;j<pCalArray[0].length;j++) {
                        System.out.print(" " + pCalArray[i][j]);
                    }
                    System.out.print("\r\n");
                }
            }
        }

        private static void meetingSlotFinder(Map<String,int[][]> personCalendar) {
            int ctr=0;
            for(Map.Entry<String, int[][]> calendar: personCalendar.entrySet()) {
                int[][] pCalArray = calendar.getValue();
                for(int j=0;j<pCalArray[0].length;j++) { // iterate over slots
                    int result = 1;
                    for(int i=0; i<pCalArray.length-1; i++) { //iterate over persons
                        ctr++;
                        result = result & pCalArray[i][j]& pCalArray[i+1][j];
                        if(result==0) break;
                    }
                    if(result == 1)
                        System.out.println("**** Meeting match at Day : " + 
                                calendar.getKey() + " and at slot: " + j);
                    else
                        System.out.println("Couldn't find any meeting match at Day : " + 
                                calendar.getKey() + " and at slot: " + j);
                }
            }
            System.out.println("#@$&* Total Iterations performed : " + ctr); 
        }

    }