查找所有与会者都可用的会议时隙的算法
在一个采访博客上遇到了这个问题。给定(a - b) i.e., from 'a' to 'b' of n people格式的免费时间表，打印所有n参与者可用的所有时间间隔。这就像一个日历应用程序，提示可能的会议时间。
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.不过，我并没有落实上述建议。我正在考虑一个最小的堆和最大的堆，在任何时候得到最小和最大。但是我担心更新开始值，因为更新堆可能会变得很昂贵。
回答 8
Stack Overflow用户
发布于 2020-09-04 22:51:53
今天面试的时候收到的。想出了一个O(N*logN)解决方案。想知道是否有可用的O(N)解决方案.
概述:将单个计划加入到一个列表中，intervals
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()Stack Overflow用户
发布于 2015-12-22 23:27:29
一个起点，仍然需要优化一点，可能是如下(代码在Python中)。您有以下数据(动态地清楚地创建allPeople列表)：
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]您可以做的是创建一个包含一天中所有时段的列表(即["0-1", "1-2", "2-3", etc.]，如下所示)：
allTimeSlots = []
for j in range(0,24):
allTimeSlots.append(str(j) + "-" + str(j+1))然后创建一个名为commonFreeSlots的列表，它由每个人的空闲时隙集合中的所有时隙组成：
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])请注意，函数parseSlot只是接受一个字符串列表(如"2-14","15-16")，并返回一个小时时隙列表(如["2-3","3-4","4-5" etc.] )，以使其与上面创建的小时时隙列表allTimeSlots相比较：
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如果运行上述脚本，将得到以下结果：
['12-13', '13-14', '18-19', '19-20']当然，为了聚合小时(并拥有['12-14','18-20']而不是每小时版本)，您仍然需要稍微工作一些输出，但我认为这应该更容易一些。
上面的解决方案应该总是有效的，但是我不确定它是最优的，它可能存在一个更好的解决方案。但是既然你还没有分享任何尝试，我想你只是想要一些提示来开始，所以我希望这个能有所帮助。
Stack Overflow用户
发布于 2020-10-27 04:27:40
我更喜欢采取一种稍微不同的方法，它是基于设置的！我会让语言元素为我带来沉重的负担。就像你们已经知道的那样，我假设所有的会议都是在一小时的顶端，间隔时间为1小时。
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))https://stackoverflow.com/questions/34425237
复制相似问题
腾讯云开发者
