为一组参与者找到最佳可能时隙的算法

Question

你建议我使用哪种算法来解决以下问题？

我想解决的问题是，根据参与者的日历可用性，找到适合所有(或几乎所有)参与者的最佳时间段。

我正在使用Java，希望能够为这些参与者安排一次会议。我将参与者当天的可用性数据分成半个小时。我想找一个所有参与者都有空的时间。

可用性问题如下所示

|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  |

我想选一个适合每个人的时间段。理想情况下，我希望算法至少选择一个选项。然后，我可以将约束应用于所选的时间，以找到最优时间。

Answer 1

可用性计划可以转换为array of bits，其中空闲为1，忙碌为0。我在下面指定了一个示例作为指导：

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

Person 1的位数组如下所示：1 | 0 | 1 | 1 | 0 | 1

由于您以30分钟为增量设置时间段，因此对于24小时的时间范围，位数组的大小不会超过48。在Java中，long数据类型足以保存此位数组的值。将参与者的每个可用时隙转换为位数组。然后，将按位运算符和应用于每个参与者的可用日程的位数组表示。结果位数组将是所有参与者的公共空闲时间。

Answer 2

安排一个类似这样的DataStructure。

地图

实际上，密钥的范围从第一天到第N天。我假设在接下来的30天内，密钥的范围将从Day1到Day30。

假设需要10个人来预订会议。而且每个人都应该在那个时间段有空位，以便预约会议。

我假设在一个8小时的工作日里有30分钟的时间。因此，一天内将有16个插槽。

因此，对于第1天->，您将把10个人的可用性保存为一个10 x 16的二维整型数组/矩阵。每个单元格将容纳0或1.0，表示此人不可用，1表示此人可用。

关键是迭代地对每个人/槽执行AND操作。(插槽0上的Person1可用性)&(插槽0上的Person2可用性)。如果为0，则立即中断循环，因为我们找不到该插槽的匹配项。如果重复AND的结果为1，则会得到特定日期的插槽的精确匹配。我已经附上了我的代码如下。打包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); 
        }

    }