schedule - 查找所有参与者都可以参加的 session 时段的算法

Question

在采访博客中遇到这个问题。给出的空闲时间时间表格式为 (a - b) i.e., from 'a' to 'b'的n人们，打印所有时间间隔 n参与者有空。它就像一个日历应用程序，建议可能的 session 时间。

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

请分享任何已知的最佳算法来解决此问题。

我正在考虑以下解决方案。

• 创建 currentList包含每个人的一个间隔的间隔。最初currentList = [4-16, 2-14, 6-8, 10-22] 。

• 查找 max_start和min_end在currentList并输出(max_start, min_end)如果max_start < min_end ;更新 currentList 中的所有间隔有start值为min_end 。删除具有 min_end 的区间来自currentList并将该人列表中的下一个条目添加到 currentList .

• 如果 max_start >= min_end在上一步中，更新 currentList 中的所有间隔有start值为max_start 。如果对于任意区间i , end > start ，将该间隔替换为 currentList与相应人的下一个间隔。

基于上述想法，对于给定的示例，它将运行如下:

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.

不过我还没有实现上述内容。我正在考虑使用最小堆和最大堆来获取任意点的最小值和最大值。但我担心更新起始值，因为更新堆可能会变得昂贵。

Answer 1

今天在采访中得到这个。提出了一个 O(N*logN) 解决方案。想知道是否有可用的 O(N) 解决方案...

概述:将各个时间表合并到一个列表中间隔 --> 按间隔的开始时间对其进行排序 --> 如果交叉则合并相邻间隔 --> 现在返回可用性很容易。

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