DSA sheet / Sorting and searching
Concert Tickets
Do these first: Apartments
The problem in brief
There are n tickets with given prices and m customers (both up to 200 000). Customers arrive one by one, each with a maximum price they are willing to pay. Each customer buys the most expensive remaining ticket priced at most their maximum, or nothing if none exists. For each customer print the price paid, or -1.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1091.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
For one customer, what question do you need answered about the remaining ticket prices? Phrase it as a search over an ordered collection.
-
“Largest value that is at most t” is a classic predecessor query. Which structures answer it quickly, and which of them also allow deleting an element?
-
If you keep the prices in a plain sorted array, binary search finds the answer fast, but deleting from the middle is slow. Can you avoid physically deleting?
-
Think of each used ticket as a hole. When a search lands on a hole, where should it go next? A union-find structure that points “left to the next free slot” makes this cheap.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The simulation is straightforward: process customers in order, pick the best ticket, remove it. Doing that with a linear scan is O(n * m) and too slow. What you need is a data structure supporting two operations in about O(log n): find the largest element at most t, and delete it. That is exactly an ordered multiset.
Where languages lack one, you can build the same behaviour from simpler parts: sort the prices once, binary search for the position of the last price at most t, and keep a “previous free slot” pointer with union-find so already-sold tickets are skipped in near-constant time. This trade (replace deletion with skipping) is a powerful trick whenever removals only ever shrink a sorted collection.
The habit: name the abstract operations your algorithm needs (predecessor query, delete), then choose the data structure that offers them.
Intuition
Tickets sit on a shelf sorted by price. A customer with budget t walks to the last ticket that is not more expensive than t, buys it, and leaves a gap. Later customers standing at the same place slide left over gaps to the next real ticket.
Approach
C++ and Java: keep the tickets in an ordered multiset (multiset / TreeMap with counts). For each customer take the greatest key at most t, output it and remove one copy; output -1 if there is none.
Python and JavaScript below: sort the prices, and give every slot a pointer p where p[k] == k means slot k is still available and otherwise p[k] points left. For a customer, binary search how many prices are at most t, then find the nearest available slot at or left of that count; slot 0 is a sentinel meaning “none”. Selling slot k sets p[k] = k - 1.
Pitfalls: the same price can appear many times, so each copy is separate; prices and budgets up to 10^9 fit in 32-bit signed ints. Output with one buffered write.
Complexity
O((n + m) log n) time. O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
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);
}
string out;
for (int i = 0; i < m; i++) {
int t;
cin >> t;
auto it = tickets.upper_bound(t);
if (it == tickets.begin()) {
out += "-1\n";
} else {
--it;
out += to_string(*it) + "\n";
tickets.erase(it);
}
}
cout << out;
return 0;
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
prices = sorted(map(int, data[2:2 + n]))
# p[k] == k means "slot k (1-based) is still for sale"; slot 0 is a sentinel for "none".
p = list(range(n + 1))
def find(k):
while p[k] != k:
p[k] = p[p[k]]
k = p[k]
return k
out = []
for i in range(m):
t = int(data[2 + n + i])
k = find(bisect_right(prices, t))
if k == 0:
out.append(-1)
else:
out.append(prices[k - 1])
p[k] = k - 1
print("\n".join(map(str, out)))
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int m = (int) st.nval;
TreeMap<Integer, Integer> tickets = new TreeMap<>();
for (int i = 0; i < n; i++) {
st.nextToken();
tickets.merge((int) st.nval, 1, Integer::sum);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
st.nextToken();
Integer key = tickets.floorKey((int) st.nval);
if (key == null) {
sb.append("-1\n");
} else {
sb.append(key).append('\n');
if (tickets.merge(key, -1, Integer::sum) == 0) tickets.remove(key);
}
}
System.out.print(sb);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const m = data[1];
const prices = Float64Array.from(data.slice(2, 2 + n)).sort();
// p[k] === k means slot k (1-based) is still for sale; slot 0 is a sentinel for "none".
const p = Int32Array.from({ length: n + 1 }, (_, k) => k);
function find(k) {
while (p[k] !== k) {
p[k] = p[p[k]];
k = p[k];
}
return k;
}
function countAtMost(t) {
let lo = 0;
let hi = n;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (prices[mid] <= t) lo = mid + 1;
else hi = mid;
}
return lo;
}
const out = [];
for (let i = 0; i < m; i++) {
const k = find(countAtMost(data[2 + n + i]));
if (k === 0) {
out.push(-1);
} else {
out.push(prices[k - 1]);
p[k] = k - 1;
}
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).