在采访博客中遇到这个问题。给定(a - b) i.e., from 'a' to 'b'人以n形式的空闲时间时间表，请打印所有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.
尽管我还没有实现上述功能。我正在考虑最小堆和最大堆以在任何时候获取最小和最大。但是我担心更新起始值，因为更新堆可能会变得很昂贵。
一个起点，还有待优化，可能如下（代码在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']代替小时版本，您当然还需要稍微处理一下输出，但是我认为这应该更容易些。
上述解决方案应始终有效，但是我不确定它是否最佳，它可能存在更好的解决方案。但是，由于您还没有分享任何尝试，我想您只是想要一些入门的技巧，所以我希望这对您有所帮助。
下面是该问题的JavaScript解决方案。它的复杂度为O（n ^ 3），但由于时间有限，因此可以认为n ^ 2
const person_1 = ['4-16', '18-24'];
const person_2 = ['2-14', '17-24'];
const person_3 = ['6-8', '12-20'];
const person_4 = ['10-22'];
const allPeople = [person_1, person_2, person_3, person_4];
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);
}
}
}
}
return allTimeSlotsInDay.filter(time => !tempResult.includes(time));
}
function getAllTimeSlots() {
const result = [];
for (let i = 0; i < 24; i = i+1) {
result.push(`${i}-${i + 1}`);
}
return result;
}
console.log(getFreeMeetingTime(allPeople));
//[ '0-1', '1-2']