Алгоритм для поиска временных интервалов встреч, где все участники доступны

Question

Нашел этот вопрос в блоге интервью. Данный свободный график в форме (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. 

Я не выполнил выше, хотя. Я думаю о минимальной куче и максимальной куче, чтобы получить минимальную и максимальную значения в любой момент. Но меня беспокоит обновление начальных значений, потому что обновление кучи может стать дорогостоящим.

Answer 1

Отправной точкой, по-прежнему оптимизирующей бит, может быть следующее (код находится на 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'] вместо почасовой версии), но это должно быть проще, я думаю.

Вышеупомянутое решение должно работать всегда, однако я не уверен, что он оптимален, он, вероятно, существует лучше. Но так как вы еще не поделились какой-либо попыткой, я думаю, вам просто понравятся несколько советов, чтобы начать работу, поэтому я надеюсь, что это поможет немного.