Backlog Leetcode Həllində Sifarişlərin sayı

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Robinlik
Geyim Yığın SimulationBaxılıb 24

Problem bəyanat

The Backlog LeetCode Həllində Sifarişlərin sayı – “Geridə qalan Sifarişlərin sayı” qeyd edir ki, 2D tam array [qiymət, məbləğ, sifariş növü] verilmişdir ki, bu da bunu ifadə edir. məbləği tipli sifarişlər verilmişdir sifariş növü.

Sifariş növüdürsə:

  • 0, cari sifarişin alış sifarişi olduğunu bildirir.
  • 1, cari sifarişin satış sifarişi olduğunu bildirir.

Nəzərə alın ki, [i] əmri i-ci sifarişdən əvvəlki bütün sifarişlər yerinə yetirildikdə yerinə yetiriləcək.

A Backlog icra olunmayan əmrlər kimi müəyyən edilir. İlkin olaraq, alış və satış sifarişləri üçün heç bir gecikmə yoxdur, aşağıdakılar baş verir:

  1. Əgər sifariş a sifariş almaq, geridə qalan ən kiçik qiymətlə satış sifarişinə baxın. Əgər satış qiyməti cari alış sifarişi qiymətindən az və ya ona bərabərdirsə, o zaman uyğunluq var və geridə qalan satış sifarişi yerinə yetirilir və silinir.
  2. Əksinə, bir olduqda sifariş satmaq, geridə qalan ən böyük qiymətə malik alış sifarişinə baxın. Əgər alış qiyməti cari satış sifarişi qiymətindən böyük və ya ona bərabərdirsə, o zaman uyğunluq var və geridə qalmış alış sifarişi yerinə yetirilir və silinir.

Ümumi məbləği qaytarmalıyıq məbləği girişdən bütün sifarişləri yerləşdirdikdən sonra geridə qalan sifarişlərin sayı. Cavab modulunu qaytarın 10^9 + 7.

Misal:

Input:  orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

Explanation:

  • Əvvəlcə 5 alış sifarişi yerləşdirilir və geridə qalan satış sifarişləri yoxdur, buna görə də bütün alış sifarişləri alış sırasına əlavə olunur.
  • 2 satış sifarişi verilir və qiymətləri 15-dən yuxarı və ya ona bərabər olan alış sifarişləri yoxdur, buna görə də bütün sifarişlər satış ehtiyatına əlavə olunur.
  • Qiyməti 1 olan 25 növ satış sifarişi verilir. Qiymətləri 25-dən böyük və ya ona bərabər olan alış sifarişləri yoxdur, ona görə də bu sifariş geri plana əlavə edilir.
  • Hər biri 4 məbləğində alış növü olan 30 sifariş verilir. Qiyməti 2 olan 15 satış sifarişi silinir. Yenə qiyməti 1 olan 25 satış sifarişi də silinir. 4-cü sifariş geridə qalan sıraya əlavə edilir, çünki geridə qalan satış sifarişləri yoxdur.
  • Nəhayət, geri planda 5 qiyməti olan 10 alış sifarişi və 1 qiyməti olan 30 alış sifarişi var. Beləliklə, geridə qalan sifarişlərin ümumi sayı 6-dır.

Backlog Leetcode Həllində Sifarişlərin sayıPin

Input:  orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Prioritet növbə or Çoxsaylı alış və ya satış sifarişlərini səmərəli şəkildə geridə qoyma və ya silmə.
  2. Qorumaq a yığın or multiset alqı-satqısı üçün ayrıca.
  3. Sifarişləri ardıcıllıqla və hər bir sifariş üçün emal etməyə başlayın:
    1. Əgər bir sifariş almaq, ən kiçik satış sifarişi qiymətindən başlayaraq qiyməti cari sifariş qiymətindən az və ya ona bərabər olan satış sifarişi qalıqlarından bütün qeydləri silin.
    2. Əksinə, əgər bu a sifariş satmaq, ən böyük alış sifarişi qiymətindən başlayaraq qiyməti cari sifariş qiymətindən böyük və ya ona bərabər olan satınalma sifarişi qalıqlarından bütün qeydləri silin.
  4. Bütün sifarişləri bitirdikdən sonra alış və satış geridə qalan sifarişlərdə mövcud olan bütün məbləğləri əlavə edin.
  5. Nəzərə alın ki, cavabımız dəyəri keçə bilər 10^9 + 7, biz cavab modulu bu sadə ədəd almaq lazımdır.

Kodu

Backlog Leetcode C++ Həllində Sifarişlərin sayı:

class Solution {
public:
    #define ll long long
    #define MOD 1000000007
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        ll ans = 0;
        multiset<pair<int,int>> sell;
        multiset<pair<int,int>,greater<pair<int,int>>> buy;
        for(auto& order:orders){
            int price = order[0],amount = order[1],orderType = order[2];
            if(orderType==0){
                while(!sell.empty() and amount>0 and sell.begin()->first<=price){
                    int available_price = sell.begin()->first;
                    int available_amount = sell.begin()->second;
                    sell.erase(sell.begin());                    
                    int take = min(amount,available_amount);                    
                    amount -= take;
                    available_amount -= take;                    
                    if(available_amount){
                        sell.insert({available_price,available_amount});
                    }
                }                
                if(amount){
                    buy.insert({price,amount});
                }
            }
            else{
                while(!buy.empty() and amount>0 and buy.begin()->first>=price){
                    int available_price = buy.begin()->first;
                    int available_amount = buy.begin()->second;
                    buy.erase(buy.begin());
                    int take = min(amount,available_amount);
                    amount -= take;
                    available_amount -= take;
                    if(available_amount){
                        buy.insert({available_price,available_amount});
                    }
                }
                if(amount){
                    sell.insert({price,amount});
                }
            }
        }
        for(auto& x:buy){
            ans += x.second;
            ans %= MOD;
        }
        for(auto& x:sell){
            ans += x.second;
            ans %= MOD;
        }
        return (int)ans;
    }
};

Backlog Leetcode Java Həllində Sifarişlərin sayı:

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        PriorityQueue<int[]> buy = new PriorityQueue<>((a, b) -> (b[0] - a[0]));
        PriorityQueue<int[]> sell = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        for (int[] order : orders) {
            if (order[2] == 0){
                buy.offer(order);
            }
            else{
                sell.offer(order);
            }
            while (!buy.isEmpty() && !sell.isEmpty() && sell.peek()[0] <= buy.peek()[0]) {
                int k = Math.min(buy.peek()[1], sell.peek()[1]);
                buy.peek()[1] -= k;
                sell.peek()[1] -= k;
                if (buy.peek()[1] == 0) buy.poll();
                if (sell.peek()[1] == 0) sell.poll();
            }

        }
        int res = 0, mod = 1000000007;
        for (int[] order : sell){
            res = (res + order[1]) % mod;
        }
        for (int[] order : buy){
            res = (res + order[1]) % mod;
        }
        return res;
    }
}

Backlog Leetcode Həllində Sifarişlərin Sayı üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (NlogN), burada N = sifarişlərin ümumi sayı. Hər bir sifariş üçün biz məlumatları multiset və ya yığına daxil edirik və tələb olunan onları silirik giriş vaxt.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N). Ən pis halda, yığının və ya multisetin ölçüsü bütün sifarişləri qəbul edə bilər.

Translate »