İşçilərin Boş vaxtı LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Airbnb Amazon alma Bloomberg ByteDance Kupanq Qapılar Facebook google Intuit Karat microsoft Kahin Pinterest Quora Snapchat Über Wayfair YahooBaxılıb 77

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

İşçilərin Boş vaxtı LeetCode Həlli – Bizə siyahı verilir schedule hər bir işçi üçün iş vaxtını əks etdirən işçilərin sayı.

Hər bir işçinin üst-üstə düşməyən siyahısı var Intervals, və bu intervallar sıralanmış qaydadadır.

Sonluların siyahısını qaytarın intervalları təmsil edən ümumi, müsbət uzunluqlu boş vaxt üçün hər işçilər, həmçinin sıralanmış qaydada.

(Baxmayaraq ki, biz təmsil edirik Intervals şəklində [x, y], içərisindəki obyektlərdir Intervals, siyahılar və ya massivlər deyil. Misal üçün, schedule[0][0].start = 1schedule[0][0].end = 2və schedule[0][0][0] müəyyən edilmir). Həmçinin [5, 5] kimi intervalları cavabımıza daxil etməyəcəyik, çünki onların uzunluğu sıfırdır.

misal

Test işi 1:

Input:

cədvəl = [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]

Çıxış:

[[3, 4]]

Izahat

Cəmi üç işçi var və bütün ümumi boş vaxt intervalları [-inf, 1], [3, 4], [10, inf] olacaqdır. Sonlu olmadığı üçün tərkibində inf olan hər hansı intervalları ləğv edirik.

Yanaşma:

Problemi addım-addım həll edək. Birincisi, fərz edək ki, hər bir işçinin yalnız bir iş vaxtı intervalı var. Fasilələri başlanğıc vaxtına görə artan qaydada sıralaya bilərik. Sonra intervalları təkrarlayırıq. İterasiya zamanı biz əvvəlki son bitmə vaxtını izləyirik. Əgər hər hansı bir interval üçün onun başlama vaxtı əvvəlki son bitmə vaxtından böyükdürsə, biz bütün işçilər üçün boş vaxt intervalı tapmışıq və onu nəticəyə əlavə edirik.

İndi hər bir işçinin birdən çox intervalı ola biləcəyi halı nəzərdən keçirək. Əvvəlcə bütün işçilərin ilk intervalını nəzərə alırıq. Bu intervalları saxlamaq və çeşidləmək üçün prioritet növbədən istifadə edə bilərik. Biz intervalları başlanğıc vaxtına görə sıralayırıq. Ən son bitmə vaxtını da izləyirik latestEnd indiyə qədər qət etmişik. Hər dəfə növbədən bir interval seçirik. Bu interval PQ-da ən kiçik başlanğıc vaxtı olan intervaldır. Cari intervalın başlama vaxtı ondan böyükdürsə latestEnd, onda biz boş vaxt intervalı tapdıq və nəticəyə müvafiq sərbəst interval əlavə edirik. Bundan sonra cari intervalın işçisində hələ də başqa intervallar qalıbsa, onu PQ-ya əlavə edirik. PQ boş qalana qədər prosesi təkrar edirik.

İşçilərin Boş vaxtı LeetCode HəlliPin

İşçilərin boş vaxtı üçün kod

Java Proqramı

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        // We store the pointers of the intervals instead of intervals themselves
        // int[]{i, j} where i represents the ith employee and
        // j represents the jth interval of the ith employee
        PriorityQueue<int[]> pq = new PriorityQueue<>(schedule.size(),
            (a, b) -> (schedule.get(a[0]).get(a[1]).start
                     - schedule.get(b[0]).get(b[1]).start));
        
        // Initialize with the first interval of all employees
        for (int i = 0; i < schedule.size(); i += 1) {
            pq.offer(new int[]{i, 0});
        }
        
        // Initialize the latest ending time
        int latestEnd = schedule.get(pq.peek()[0]).get(0).end;
        
        List<Interval> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            int[] indices = pq.poll();
            List<Interval> employee = schedule.get(indices[0]);
            Interval cur = employee.get(indices[1]);
            
            if (cur.start > latestEnd) {
                res.add(new Interval(latestEnd, cur.start));
            }
            
            if (indices[1] < employee.size() - 1) {
                pq.offer(new int[]{indices[0], indices[1] + 1});
            }
            latestEnd = Math.max(latestEnd, cur.end);
        }
        return res;
    }
}

C ++ Proqramı

/*
// Definition for an Interval.
class Interval {
public:
    int start;
    int end;

    Interval() {}

    Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        const int _inf = -1, inf = 1e9;
    auto getFreeTime = [&](vector<Interval> &inv) {
      int prevEn = -1;
      vector<Interval> freeTime;
      for (Interval &i: inv) {
        freeTime.push_back(Interval(prevEn, i.start));
        prevEn = i.end;
      }
      freeTime.push_back(Interval(prevEn, inf));
      return freeTime;
    };
    auto getCommon = [](vector<Interval> &a, vector<Interval> &b) {
      int n = a.size(), m = b.size(), i = 0, j = 0;
      vector<Interval> common;
      while (i < n && j < m) {
        int st = max(a[i].start, b[j].start), en = min(a[i].end, b[j].end);
        if (en > st) {
          common.push_back(Interval(st, en));
        }
        if (a[i].end < b[j].end) i++;
        else j++;
      }
      return common;
    }; 
    for (vector<Interval> &inv: schedule) {
      inv = getFreeTime(inv);
    }
    vector<Interval> common = {Interval(_inf, inf)};
    for (vector<Interval> &inv: schedule) {
      common = getCommon(common, inv);
    }
    vector<Interval> ans;
    for (Interval &i: common) {
      if (i.start == _inf || i.end == inf) continue;
      ans.push_back(i);
    }
    return ans;
    }
};

İşçilərin Boş Zamanı üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi: O(N·logK) burada N intervalların ümumi sayı, K isə işçilərin sayıdır. PQ-ni K intervalları ilə işə salırıq, burada K işçilərin sayıdır. Hər döngədə biz növbədən bir elementi sorğulayırıq və növbəyə ən çoxu bir element əlavə edə bilərik və ya əlavə etməyə də bilərik. Buna görə də PQ-nun ölçüsü K-dən böyük deyil. Biz bunu N interval üçün təkrar edəcəyik.
Kosmik mürəkkəblik: O (N)

Crack Sistemi Dizayn Müsahibələri
Translate »