Concert Tickets
Concert Tickets
There are \(n\) concert tickets, each with a price. Then \(m\) customers arrive, one after another.
Each customer says the maximum price that they are willing to pay. The customer gets the ticket with the largest price that does not exceed their maximum price, and that ticket cannot be sold again.
Constraints:
- \(1 \le n, m \le 2 \cdot 10^5\)
- \(1 \le h_i, t_i \le 10^9\)
Input:
- First line: two integers \(n\) and \(m\).
- Second line: \(n\) integers \(h_1, h_2, \ldots, h_n\) — the ticket prices.
- Third line: \(m\) integers \(t_1, t_2, \ldots, t_m\) — the maximum price of each customer, in the order they arrive.
Output:
- For each customer, one line with the price that they pay, or \(-1\) if they cannot get a ticket.
Example:
Input:
5 3
5 3 7 8 5
4 8 3
Output:
3
8
-1
Solution
We need a structure that keeps the remaining prices sorted, finds the largest price \(\le t\), and deletes one price. A multiset does all three in \(O(\log n)\). A set is not enough, because several tickets can have the same price.
tickets.upper_bound(t)returns the first price that is greater than \(t\).- If this is the first element, every ticket costs more than \(t\), and the answer is \(-1\).
- Otherwise the element just before it is the largest price \(\le t\).
We delete the sold ticket with erase(it), using the iterator. erase(value) would delete all tickets with that price.
The time complexity is \(O((n + m) \log n)\).
#include <iostream>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
multiset<int> tickets;
for (int i = 0; i < n; i++) {
int h;
cin >> h;
tickets.insert(h);
}
for (int i = 0; i < m; i++) {
int t;
cin >> t;
// the first ticket with price greater than t
auto it = tickets.upper_bound(t);
if (it == tickets.begin()) {
cout << -1 << "\n"; // every ticket is too expensive
} else {
it--; // the most expensive ticket with price at most t
cout << *it << "\n";
tickets.erase(it); // erase only this one ticket
}
}
}