İş Planlaşdırması Leetcode Həllində Maksimum Mənfəət

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Airbnb Amazon Atlassian Qapılar google microsoft Swiggy Über
Geyim İkili axtarış Dinamik proqramlaşdırma çeşidləyiciBaxılıb 51

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

The LeetCode Həllində İş Planlaşdırmasında Maksimum Mənfəət – “İş Planlaşdırmasında Maksimum Mənfəət” sizə verildiyini bildirir n hər bir işin haradan başladığı işlər başlanğıc vaxtı[i] və bitir bitmə vaxtı[i] və mənfəət əldə etmək mənfəət[i].

Biz əldə edə biləcəyimiz maksimum qazancı qaytarmalıyıq ki, heç bir iki seçilmiş iş üst-üstə düşməsin. Həmçinin, əgər bir iş a vaxt x, onda biz bir anda başqa işə başlaya bilərik x-dən böyük və ya bərabərdir.

Misal:

İş Planlaşdırması Leetcode Həllində Maksimum MənfəətPin

Input:  startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

Explanation:

  • Birinci və dördüncü işləri seçsək, 120 qazanc əldə edə bilərik və bu, əldə edə biləcəyimiz maksimum qazancdır.
  • Qeyd edək ki, birinci və dördüncü işlər üst-üstə düşmədiyi üçün eyni vaxtda edilə bilər.
Input:  startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150

Explanation:

  • Birinci, dördüncü və beşinci işi seçsək, maksimum 150 qazanc əldə edəcəyik.
  • Qeyd edək ki, seçilmiş alt çoxluq üst-üstə düşmür.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir dinamik proqramlaşdırmaikili axtarış.
  2. İlk növbədə, bizə lazımdır cür iş yerləri azalmayan sifariş onların bitmə vaxtı vasitəsilə maksimum mənfəəti asanlıqla hesablamağa kömək edəcək dinamik proqramlaşdırma.
  3. Qoy dp[i] = ilk i+1 işləri nəzərə alsaq, əldə edə biləcəyimiz maksimum qazanc.
  4. Hər indeks üçün iki hal var:
    1. Cari işi seçin: Əgər cari işi seçsək, bu iş başlanğıc vaxtından[i] başlayacaq. Beləliklə, əldə edə biləcəyimiz maksimum qazanc budur cari mənfəət + dp[j]. dp[j] ən böyük j indeksidir ki, endTime[j] startTime[i]-dən kiçik və ya ona bərabərdir və j i-dən ciddi şəkildə kiçik olmalıdır. Qeyd edək ki, əgər etibarlı j varsa, o zaman dp[i] = cari mənfəət + dp[j] əks halda, dp[i] = cari mənfəət.
      1. Ən böyük j indeksini elə hesablamaq üçün endTime[i] startTime[i] və j-dən kiçik və ya ona bərabər olsun ikili axtarış uyğun indeksi tapmaq üçün iş yerləri artıq bitmə vaxtına görə azalmayan qaydada sıralanır.
    2. Cari işi seçməyin: Bu halda, dp[i] = dp[i-1].
  5. götürməliyik yuxarıda göstərilən hər iki halın maksimumu hər bir indeks üçün dəyərləri hesablamaq üçün.
  6. Cavabımız dp[n-1] olacaq.

Kodu

Leetcode C++ Həllində İş Planlaşdırmasında Maksimum Mənfəət:

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs;
        for(int i=0;i<n;i++){
            jobs.push_back({startTime[i],endTime[i],profit[i]});
        }
        sort(jobs.begin(),jobs.end(),[&](const vector<int>& a,const vector<int>& b){
           if(a[1]==b[1]){
               return a[0] < b[0];
           } 
           return a[1] < b[1];
        });
        vector<int> dp(n);
        dp[0] = jobs[0][2];
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1];
            int l = 0,r = i - 1,prev = 0;
            while(l<=r){
                int mid = (l+r)/2;
                if(jobs[mid][1]<=jobs[i][0]){
                    prev = dp[mid];
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
            dp[i] = max(dp[i],jobs[i][2]+prev);
        }
        return dp[n-1];
    }
};

Leetcode Java Həllində İş Planlaşdırmasında Maksimum Mənfəət:

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for(int i=0;i<n;i++){
            jobs[i] = new int[] {startTime[i],endTime[i],profit[i]};
        }
        Arrays.sort(jobs,(a,b)->a[1]-b[1]);
        int[] dp = new int[n];
        dp[0] = jobs[0][2];
        for(int i=1;i<n;i++){
            dp[i] = dp[i-1];
            int l = 0,r = i - 1,prev = 0;
            while(l<=r){
                int mid = (l+r)/2;
                if(jobs[mid][1]<=jobs[i][0]){
                    prev = dp[mid];
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
            dp[i] = Math.max(dp[i],jobs[i][2]+prev);
        }
        return dp[n-1];
    }
}

İş Planlaması Leetcode Həllində Maksimum Mənfəət üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (NlogN) bütün giriş massivini bir dəfə və hər bir indeks üçün keçdiyimiz üçün ikili axtarışı tətbiq edirik. Burada N = giriş massivinin ölçüsü.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N). Hesablanmış dəyərləri saxlamaq üçün xətti massivdən istifadə edirik.

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