Greedy with Sets and Ordered Maps

Ordered containers find a feasible neighbor, not just a global minimum or maximum. We allocate ticket prices to arriving customers: for each budget, sell the most expensive remaining ticket not exceeding that budget. A multiset preserves duplicate tickets and supports predecessor queries in logarithmic time. The same choice also maximizes the number of served customers under these upper-budget constraints, as an exchange argument explains.

Prerequisites: Sets and Maps; lower_bound/upper_bound; exchange arguments. Related existing lessons: Sets and Maps.

Build the idea

1. Translate the query

   upper_bound(B) points to the first price strictly greater than budget B. Its predecessor is the largest affordable ticket. If upper_bound equals begin(), no ticket is affordable and we return −1. lower_bound instead finds the first price at least a key, useful for lower-threshold matching; confusing these directions changes feasibility.

2. Preserve multiplicity

   A multiset stores each ticket copy. Erase the chosen iterator to remove exactly one copy. erase(value) would remove every equal price and could incorrectly deny later customers. The input order of customers is fixed; the code does not sort requests. Ordered maps can attach counts or IDs, but then their updates must maintain the same remaining-resource invariant.

   $$T=\max \{\mathrm{remainingPrice}\le \mathrm{budget}\}$$

3. Correctness proof: preserve future flexibility

   Take an optimal maximum-served matching agreeing with earlier greedy allocations. For the current customer, let greedy choose largest affordable T. If the optimum uses cheaper S, substitute T; if T was reserved for a future customer, move S to that customer, who could afford T and therefore also S. If the current customer was unmatched but T was used later, move it here without changing cardinality. If T was unused, serving the customer cannot hurt. Thus an optimum agrees with the choice. If no affordable ticket remains, no matching agreeing with the prefix can serve this customer.

4. Trace the sample

   Tickets are [5,3,7,8,5] and budgets [4,8,5]. The first customer receives 3, the largest affordable price. The second receives 8. The third receives one copy of 5, leaving the other 5 and 7. A set would collapse the two 5 tickets; a max-heap could hide an unaffordable maximum without directly providing its predecessor.

5. State the optimization limits

   The prescribed service rule and maximum served count have the shown exchange structure. Do not assume the same query optimizes arbitrary customer utilities, ticket-specific compatibility or future reservations. A lower-threshold resource problem may instead need the smallest sufficiently large item. Derive which feasible extreme saves flexibility before choosing lower_bound or upper_bound.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<set>
int main(){
    int n,m;
    std::cin>>n>>m;
    std::multiset<long long>tickets;
    for(int i=0;i<n;++i){
        long long p;
        std::cin>>p;
        tickets.insert(p);
    }
    for(int i=0;i<m;++i){
        long long budget;
        std::cin>>budget;
        auto it=tickets.upper_bound(budget);
        if(it==tickets.begin()){
            std::cout<<-1<<'\n';
        }
        else{
            --it;
            std::cout<<*it<<'\n';
            tickets.erase(it);
        }
    } // Iterator erasure removes one copy, not every equal price.
}

Complexity analysis

O(n log n) insertion and O(m log(n+1)) queries/erases, O(n) ticket storage. Each request uses one upper_bound and at most one iterator decrement/erase. No sum can overflow because the output is a single stored price per request.

Example input and output

Read n m (0..100000 each), then n ticket prices in 0..10^9 and m customer budgets in 0..10^9. For each customer in input order print largest affordable remaining price, or −1.

Input

5 3
5 3 7 8 5
4 8 5

Output

3
8
5

The predecessor queries select 3,8,5 and erase only the sold copies.

Practical applications

Use ordered sets/maps for predecessor/successor-based greedy allocation, price matching and nearest feasible slots. A heap handles an extreme but not arbitrary bound queries; a Fenwick tree over compressed counts can support similar selection when the value universe is known.

Check your understanding

Why call tickets.erase(it) rather than tickets.erase(*it)?

Put it into practice

Check outputs against a simple list that scans all remaining prices.