✏️
leetcode solution
  • Leetcode Solutions
  • LeetCode 1. Two Sum
  • LeetCode 2. Add Two Numbers
  • LeetCode 3. Longest Substring Without Repeating Characters
  • LeetCode 4. Median of Two Sorted Arrays
  • LeetCode 5. Longest Palindromic Substring
  • LeetCode 6. ZigZag Conversion
  • LeetCode 7. Reverse Integer
  • LeetCode 8. String to Integer (atoi)
  • LeetCode 9. Palindrome Number
  • LeetCode 10. Regular Expression Matching
  • LeetCode 11. Container With Most Water
  • LeetCode 12. Integer to Roman
  • LeetCode 13. Roman to Integer
  • LeetCode 14. Longest Common Prefix
  • LeetCode 15. 3Sum
  • LeetCode 16. 3Sum Closest
  • LeetCode 17. Letter Combinations of a Phone Number
  • LeetCode 18. 4Sum
  • LeetCode 19. Remove Nth Node From End of List
  • LeetCode 20. Valid Parentheses
  • LeetCode 21. Merge Two Sorted Lists
  • LeetCode 22. Generate Parentheses
  • LeetCode 23. Merge k Sorted Lists
  • LeetCode 24. Swap Nodes in Pairs
  • LeetCode 25. Reverse Nodes in k-Group
  • LeetCode 26. Remove Duplicates from Sorted Array
  • LeetCode 27. Remove Element
  • LeetCode 28. Implement strStr()
  • LeetCode 29. Divide Two Integers
  • LeetCode 30. Substring with Concatenation of All Words
  • LeetCode 31. Next Permutation
  • LeetCode 32. Longest Valid Parentheses
  • LeetCode 33. Search in Rotated Sorted Array
  • LeetCode 42. Trapping Rain Water
  • LeetCode 56. Merge Intervals
  • LeetCode 67. Add Binary
  • LeetCode 81. Search in Rotated Sorted Array II
  • LeetCode 124. Binary Tree Maximum Path Sum
  • LeetCode 125. Valid Palindrome
  • LeetCode 153. Find Minimum in Rotated Sorted Array
  • LeetCode 154. Find Minimum in Rotated Sorted Array II
  • LeetCode 157. Read N Characters Given Read4
  • LeetCode 158. Read N Characters Given Read4 II - Call multiple times
  • LeetCode 236. Lowest Common Ancestor of a Binary Tree
  • LeetCode 238. Product of Array Except Self
  • LeetCode 269. Alien Dictionary
  • Leetcode 295. Find Median from Data Stream
  • Leetcode 297. Serialize and Deserialize Binary Tree
  • LeetCode 300. Longest Increasing Subsequence
  • LeetCode 301. Remove Invalid Parentheses
  • LeetCode 336. Palindrome Pairs
  • LeetCode 407. Trapping Rain Water II
  • LeetCode 415. Add Strings
  • LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
  • LeetCode 489. Robot Room Cleaner
  • LeetCode 560. Subarray Sum Equals K
  • LeetCode 680. Valid Palindrome II
  • LeetCode 710. Random Pick with Blacklist
  • LeetCode 721. Accounts Merge
  • LeetCode 863. All Nodes Distance K in Binary Tree
  • LeetCode 918. Maximum Sum Circular Subarray
  • LeetCode 953. Verifying an Alien Dictionary
  • LeetCode 973. K Closest Points to Origin
  • LeetCode 1249. Minimum Remove to Make Valid Parentheses
  • LeetCode 1428. Leftmost Column with at Least a One
  • LeetCode 1570. Dot Product of Two Sparse Vectors
  • LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
  • LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
  • LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
  • Leetcode 1727. Largest Submatrix With Rearrangements
  • LeetCode 1751. Maximum Number of Events That Can Be Attended II
  • LeetCode 1754. Largest Merge Of Two Strings
  • LeetCode 1755. Closest Subsequence Sum
  • LeetCode 1760. Minimum Limit of Balls in a Bag
  • LeetCode 1761. Minimum Degree of a Connected Trio in a Graph
  • LeetCode 1764. Form Array by Concatenating Subarrays of Another Array
  • LeetCode 1765. Map of Highest Peak
  • LeetCode 1766. Tree of Coprimes
  • LeetCode 1770. Maximum Score from Performing Multiplication Operations
  • LeetCode 1771. Maximize Palindrome Length From Subsequences
  • LeetCode 1774. Closest Dessert Cost
  • LeetCode. 1775 Equal Sum Arrays With Minimum Number of Operations
  • LeetCode 1776. Car Fleet II
  • LeetCode 1778. Shortest Path in a Hidden Grid
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
  • LeetCode 1780. Check if Number is a Sum of Powers of Three
  • LeetCode 1781. Sum of Beauty of All Substrings
  • LeetCode 1782. Count Pairs Of Nodes
  • LeetCode 1784. Check if Binary String Has at Most One Segment of Ones
  • LeetCode 1785. Minimum Elements to Add to Form a Given Sum
  • LeetCode 1786. Number of Restricted Paths From First to Last Node
  • LeetCode 1787. Make the XOR of All Segments Equal to Zero
  • LeetCode 1788. Maximize the Beauty of the Garden
  • LeetCode 1790. Check if One String Swap Can Make Strings Equal
  • LeetCode 1791. Find Center of Star Graph
  • LeetCode 1792. Maximum Average Pass Ratio
  • LeetCode 1793. Maximum Score of a Good Subarray
  • LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference
  • LeetCode 1796. Second Largest Digit in a String
  • LeetCode 1797. Design Authentication Manager
  • LeetCode 1798. Maximum Number of Consecutive Values You Can Make
  • LeetCode 1799. Maximize Score After N Operations
  • LeetCode 1800. Maximum Ascending Subarray Sum
  • LeetCode 1801. Number of Orders in the Backlog
  • LeetCode 1802. Maximum Value at a Given Index in a Bounded Array
  • LeetCode 1803. Count Pairs With XOR in a Range
  • LeetCode 1804. Implement Trie II (Prefix Tree)
  • LeetCode 1805. Number of Different Integers in a String
  • LeetCode 1807. Evaluate the Bracket Pairs of a String
  • LeetCode 1808. Maximize Number of Nice Divisors
  • LeetCode 1810. Minimum Path Cost in a Hidden Grid
  • LeetCode 1812. Determine Color of a Chessboard Square
  • LeetCode 1813. Sentence Similarity III
  • LeetCode 1814. Count Nice Pairs in an Array
  • LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts
  • LeetCode 1816. Truncate Sentence
  • LeetCode 1817. Finding the Users Active Minutes
  • LeetCode 1818. Minimum Absolute Sum Difference
  • LeetCode 1819. Number of Different Subsequences GCDs
  • LeetCode 1820. Maximum Number of Accepted Invitations
  • LeetCode 1822. Sign of the Product of an Array
  • LeetCode 1824. Minimum Sideway Jumps
  • LeetCode 1825. Finding MK Average
  • LeetCode 1826. Faulty Sensor
  • LeetCode 1827. Minimum Operations to Make the Array Increasing
  • LeetCode 1828. Queries on Number of Points Inside a Circle
  • LeetCode 1829. Maximum XOR for Each Query
  • LeetCode 1830. Minimum Number of Operations to Make String Sorted
  • LeetCode 1832. Check if the Sentence Is Pangram
  • LeetCode 1833. Maximum Ice Cream Bars
  • LeetCode 1834. Single-Threaded CPU
  • LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND
  • LeetCode 1836. Remove Duplicates From an Unsorted Linked List
  • LeetCode 1837. Sum of Digits in Base K
  • LeetCode 1839. Longest Substring Of All Vowels in Order
  • LeetCode 1840. Maximum Building Height
  • LeetCode 1847. Closest Room
  • LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
  • LeetCode 1851. Minimum Interval to Include Each Query
Powered by GitBook
On this page

Was this helpful?

LeetCode 1801. Number of Orders in the Backlog

Priority Queue

PreviousLeetCode 1800. Maximum Ascending Subarray SumNextLeetCode 1802. Maximum Value at a Given Index in a Bounded Array

Last updated 4 years ago

Was this helpful?

You are given a 2D integer array orders, where each orders[i] = [pricei, amounti, orderTypei] denotes that amounti orders have been placed of type orderTypei at the price pricei. The orderTypei is:

  • 0 if it is a batch of buy orders, or

  • 1 if it is a batch of sell orders.

Note that orders[i] represents a batch of amounti independent orders with the same price and order type. All orders represented by orders[i] will be placed before all orders represented by orders[i+1] for all valid i.

There is a backlog that consists of orders that have not been executed. The backlog is initially empty. When an order is placed, the following happens:

  • If the order is a buy order, you look at the sell order with the smallest price in the backlog. If that sell order's price is smaller than or equal to the current buy order's price, they will match and be executed, and that sell order will be removed from the backlog. Else, the buy order is added to the backlog.

  • Vice versa, if the order is a sell order, you look at the buy order with the largest price in the backlog. If that buy order's price is larger than or equal to the current sell order's price, they will match and be executed, and that buy order will be removed from the backlog. Else, the sell order is added to the backlog.

Return the total amount of orders in the backlog after placing all the orders from the input. Since this number can be large, return it modulo 109 + 7.

Example 1:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation: Here is what happens with the orders:
- 5 orders of type buy with price 10 are placed. There are no sell orders, so the 5 orders are added to the backlog.
- 2 orders of type sell with price 15 are placed. There are no buy orders with prices larger than or equal to 15, so the 2 orders are added to the backlog.
- 1 order of type sell with price 25 is placed. There are no buy orders with prices larger than or equal to 25 in the backlog, so this order is added to the backlog.
- 4 orders of type buy with price 30 are placed. The first 2 orders are matched with the 2 sell orders of the least price, which is 15 and these 2 sell orders are removed from the backlog. The 3rd order is matched with the sell order of the least price, which is 25 and this sell order is removed from the backlog. Then, there are no more sell orders in the backlog, so the 4th order is added to the backlog.
Finally, the backlog has 5 buy orders with price 10, and 1 buy order with price 30. So the total number of orders in the backlog is 6.

Example 2:

Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984
Explanation: Here is what happens with the orders:
- 109 orders of type sell with price 7 are placed. There are no buy orders, so the 109 orders are added to the backlog.
- 3 orders of type buy with price 15 are placed. They are matched with the 3 sell orders with the least price which is 7, and those 3 sell orders are removed from the backlog.
- 999999995 orders of type buy with price 5 are placed. The least price of a sell order is 7, so the 999999995 orders are added to the backlog.
- 1 order of type sell with price 5 is placed. It is matched with the buy order of the highest price, which is 5, and that buy order is removed from the backlog.
Finally, the backlog has (1000000000-3) sell orders with price 7, and (999999995-1) buy orders with price 5. So the total number of orders = 1999999991, which is equal to 999999984 % (109 + 7).

Constraints:

  • 1 <= orders.length <= 10^5

  • orders[i].length == 3

  • 1 <= pricei, amounti <= 10^9

  • orderTypei is either 0 or 1.

Solution

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        auto cmp1 = [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        };
        auto cmp2 = [](const vector<int> &a, const vector<int> &b) {
            return a[0] > b[0];
        };

        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp1)> buy_backlog(cmp1);
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp2)> sell_backlog(cmp2);
        
        for (vector<int> order : orders) {
            if (order[2] == 0) {
                // buy order
                while (order[1] > 0 && !sell_backlog.empty()) {
                    if (sell_backlog.top()[0] > order[0]) {
                        break;
                    }
                    vector<int> sell_order = sell_backlog.top();
                    sell_backlog.pop();
                    
                    if (order[1] >= sell_order[1]) {
                        order[1] -= sell_order[1];
                    } else {
                        sell_order[1] -= order[1];
                        order[1] = 0;
                        sell_backlog.push(sell_order);
                    }
                }
                if (order[1] > 0) {
                    buy_backlog.push(order);
                }
            } else {
                while (order[1] > 0 && !buy_backlog.empty()) {
                    if (buy_backlog.top()[0] < order[0]) {
                        break;
                    }
                    vector<int> buy_order = buy_backlog.top();
                    buy_backlog.pop();
                    
                    if (order[1] >= buy_order[1]) {
                        order[1] -= buy_order[1];
                    } else {
                        buy_order[1] -= order[1];
                        order[1] = 0;
                        buy_backlog.push(buy_order);
                    }
                }
                if (order[1] > 0) {
                    sell_backlog.push(order);
                }
            }
        }
        
        int mod = 1e9+7;
        int ans = 0;
        while (!buy_backlog.empty()) {
            ans += buy_backlog.top()[1];
            ans %= mod;
            buy_backlog.pop();
        }
        while (!sell_backlog.empty()) {
            ans += sell_backlog.top()[1];
            ans %= mod;
            sell_backlog.pop();
        }
        return ans;
    }
};