1229. Meeting Scheduler

LeetCode medium original: C# #array #csharp #leetcode #math #medium #sort #two-pointers
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

given Arrayы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, return самый ранний временной слот, который подходит обоим и имеет продолжительность duration.

Если нет общего временного слота, который удовлетворяет требованиям, return пустой Array.

Формат временного слота — это Array из двух elementов [start, end], представляющий инклюзивный временной диапазон от start до end.

Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.

Beispiel:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8

Output: [60,68]

C# Lösung

zugeordnet/original 
public class Solution {
    public IList<int> MinAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Array.Sort(slots1, (a, b) => a[0].CompareTo(b[0]));
        Array.Sort(slots2, (a, b) => a[0].CompareTo(b[0]));
        
        int pointer1 = 0, pointer2 = 0;
        
        while (pointer1 < slots1.Length && pointer2 < slots2.Length) {
            int intersectLeft = Math.Max(slots1[pointer1][0], slots2[pointer2][0]);
            int intersectRight = Math.Min(slots1[pointer1][1], slots2[pointer2][1]);
            
            if (intersectRight - intersectLeft >= duration) {
                return new List<int> { intersectLeft, intersectLeft + duration };
            }
            
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        return new List<int>();
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> MinAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Array.Sort(slots1, (a, b) => a[0].CompareTo(b[0]));
        Array.Sort(slots2, (a, b) => a[0].CompareTo(b[0]));
        
        int pointer1 = 0, pointer2 = 0;
        
        while (pointer1 < slots1.size() && pointer2 < slots2.size()) {
            int intersectLeft = max(slots1[pointer1][0], slots2[pointer2][0]);
            int intersectRight = min(slots1[pointer1][1], slots2[pointer2][1]);
            
            if (intersectRight - intersectLeft >= duration) {
                return new List<int> { intersectLeft, intersectLeft + duration };
            }
            
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        return new List<int>();
    }
}

Java Lösung

zugeordnet/original 
class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);

        int pointer1 = 0, pointer2 = 0;

        while (pointer1 < slots1.length && pointer2 < slots2.length) {
            int intersectLeft = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
            int intersectRight = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
            if (intersectRight - intersectLeft >= duration) {
                return new ArrayList<Integer>(Arrays.asList(intersectLeft, intersectLeft + duration));
            }
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++;
            } else {
                pointer2++;
            }
        }
        return new ArrayList<Integer>();
    }
}

JavaScript Lösung

zugeordnet/original 
var minAvailableDuration = function(slots1, slots2, duration) {
    slots1.sort((a, b) => a[0] - b[0]);
    slots2.sort((a, b) => a[0] - b[0]);
    
    let pointer1 = 0, pointer2 = 0;
    
    while (pointer1 < slots1.length && pointer2 < slots2.length) {
        let intersectLeft = Math.max(slots1[pointer1][0], slots2[pointer2][0]);
        let intersectRight = Math.min(slots1[pointer1][1], slots2[pointer2][1]);
        
        if (intersectRight - intersectLeft >= duration) {
            return [intersectLeft, intersectLeft + duration];
        }
        
        if (slots1[pointer1][1] < slots2[pointer2][1]) {
            pointer1++;
        } else {
            pointer2++;
        }
    }
    return [];
};

Python Lösung

zugeordnet/original 
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 []

Go Lösung

zugeordnet/original 
func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
    sort.Slice(slots1, func(i, j int) bool {
        return slots1[i][0] < slots1[j][0]
    })
    sort.Slice(slots2, func(i, j int) bool {
        return slots2[i][0] < slots2[j][0]
    })
    
    pointer1, pointer2 := 0, 0
    
    for pointer1 < len(slots1) && pointer2 < len(slots2) {
        intersectLeft := max(slots1[pointer1][0], slots2[pointer2][0])
        intersectRight := min(slots1[pointer1][1], slots2[pointer2][1])
        
        if intersectRight - intersectLeft >= duration {
            return []int{intersectLeft, intersectLeft + duration}
        }
        
        if slots1[pointer1][1] < slots2[pointer2][1] {
            pointer1++
        } else {
            pointer2++
        }
    }
    return []int{}
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

Отсортируйте оба Arrayа slots1 и slots2 по времени начала.

Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.

Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:

find общий слот между slots1[pointer1] и slots2[pointer2].

Если общий слот больше или равен duration, return результат.

В противном случае find слот, который заканчивается раньше, и передвиньте указатель.

Если общий слот не найден, return пустой Array.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.