LC: 1229. Meeting Scheduler
https://leetcode.com/problems/meeting-scheduler/
1229. Meeting Scheduler
Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.
If there is no common time slot that satisfies the requirements, return an empty array.
The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.
It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.
Example 1:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]Example 2:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []Constraints:
1 <= slots1.length, slots2.length <= 104slots1[i].length, slots2[i].length == 2slots1[i][0] < slots1[i][1]slots2[i][0] < slots2[i][1]0 <= slots1[i][j], slots2[i][j] <= 1091 <= duration <= 106
The Essence:
Die Grundlage der Lösung soll die folgende Logik implementieren:
Wir sollen von allen Intervallen zwei finden, die sich schneiden, wobei es nicht wichtig ist, zu wem diese Intervalle gehören. (Wenn sich zwei Intervalle schneiden, können sie gemäß den Einschränkungen nicht derselben Person gehören.)
Wir sollen die Zeitdauer dieser ĂĽberlappenden Intervalle berechnen.
Wenn diese Zeitdauer länger als die Gesuchte ist, geben wir die Anfangszeit dieses Intervalls und die angegebene Dauer zu dieser Startzeit (als Endzeit) zurück. Die angegebenen Intervalle sind nicht sortiert. Um das frühesten mögliche Intervall zu finden, müssen wir diese irgendwie in aufsteigender Reihenfolge verarbeiten.
Details:
In einem gemeinsamen Intervall ist die Intervalldauer durch min(end1, end2) - max(start1, start2) gegeben. Wenn die Startzeiten in sortierter Reihenfolge verarbeitet werden und die gefundene Zeitdauer länger als k ist, sollte das Intervall [max(start1, start2), max(start1, start2)+k] zurückgegeben werden.
Um die Intervalle sortiert zu verarbeiten, können die vorgegebenen Listen sortiert oder eine Prioritätsschlange verwendet werden. Für die Prioritätsschlange kann ein Vergleich von gepollten und nachgesehenen Intervallen verwendet werden. Für die Sortierungsimplementation ist die Verwendung der Zwei-Zeiger-Technik eine gute Möglichkeit.
Solution(s):
The code of these approaches can be found here:
Default Code:
Last updated