Сложность: medium
Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration.
Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив.
Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.
Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.
Пример:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]
👨💻 Алгоритм:
1⃣Отсортируйте оба массива slots1 и slots2 по времени начала.
2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.
3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:
Найдите общий слот между slots1[pointer1] и slots2[pointer2].
Если общий слот больше или равен duration, верните результат.
В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель.
Если общий слот не найден, верните пустой массив.
😎 Решение:
class Solution:
def minAvailableDuration(self, slots1, slots2, duration):
slots1.sort(key=lambda x: x[0])
slots2.sort(key=lambda x: x[0])
pointer1, pointer2 = 0, 0
while pointer1 < len(slots1) and pointer2 < len(slots2):
intersect_left = max(slots1[pointer1][0], slots2[pointer2][0])
intersect_right = min(slots1[pointer1][1], slots2[pointer2][1])
if intersect_right - intersect_left >= duration:
return [intersect_left, intersect_left + duration]
if slots1[pointer1][1] < slots2[pointer2][1]:
pointer1 += 1
else:
pointer2 += 1
return []
Ставь 👍 и забирай 📚 Базу знаний