Problem link ও উৎস
- **Original source:** CSES Sorting and Searching — ordered-multiset query
- **Platform:** CSES Problem Set —
("Concert Tickets")
- **Topic:** heap / priority queue (ordered multiset thinking)
- **Difficulty:** Medium
- **Pattern:** Ordered multiset / "best ≤ x then remove" query
- **Basic idea inherited from:** `05-hashing` / sorted structures — একটা balanced ordered collection-এ predecessor query + delete
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n`-টা concert ticket আছে, প্রতিটার একটা দাম। `m`-জন customer আসে এক এক করে; প্রত্যেকের একটা সর্বোচ্চ বাজেট `max_price`। প্রতিটা customer তার বাজেটের **মধ্যে যে ticket-টার দাম সবচেয়ে বেশি** (অর্থাৎ `<= max_price`-এর মধ্যে largest) সেটা কেনে, আর সেই ticket চলে যায়। বাজেটের মধ্যে কোনো ticket না থাকলে সে কিছু কেনে না। প্রতিটা customer কত দাম দিল (বা না কিনলে `-1`) সেটা order-এ return করো।
```text
tickets = [5, 3, 7, 8, 5], customers = [4, 8, 3] -> [3, 8, -1]
```
### Input ও output {#8-example-input-and-output}
```text
Input : tickets=[5,3,7,8,5], customers=[4,8,3] -> Output: [3, 8, -1]
Input : tickets=[2], customers=[1] -> Output: [-1] (বাজেট কম)
Input : tickets=[2], customers=[2] -> Output: [2] (ঠিক bound)
Input : tickets=[1,1,1], customers=[1,1,1,1] -> Output: [1, 1, 1, -1] (stock শেষ)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা দোকানে নানা দামের ticket তাকে সাজানো — সস্তা থেকে দামি। একজন ক্রেতা এসে বলে "আমার বাজেট 4"; বিক্রেতা তাকের যে ticket-গুলো 4-এর মধ্যে, তাদের মধ্যে **সবচেয়ে দামিটা** তুলে দেন, সেটা তাক থেকে সরে যায়। বাজেটের নিচে কিছু না থাকলে খালি হাতে ফেরত। "এই দামের নিচে সবচেয়ে দামিটা চট করে দাও আর সরিয়ে নাও" — সেই sorted তাকটাই ordered multiset।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `05-hashing`/sorted-structures-এর ধারণা — একটা **ordered collection**-এ দুটো কাজ বারবার লাগে: (1) "x-এর `<=` সবচেয়ে বড় element কোনটা?" (predecessor query) আর (2) "সেটা remove করো"। একটা plain heap শুধু global max/min দেয়; এখানে দরকার "একটা bound-এর নিচে best", তাই একটা balanced ordered structure (বা sorted list + bisect) লাগে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: এটা একটা **greedy assignment** — প্রতিটা customer-কে তার বাজেটের ঠিক-নিচের সবচেয়ে দামি ticket দেওয়া কখনো খারাপ না, কারণ প্রশ্নই বলছে প্রত্যেকে নিজে নিজে সর্বোচ্চ-affordable নেয় (এটা একটা per-customer rule, global optimization না)। মূল কাজটা data-structural: প্রতিবার একটা ordered set-এ "`<= x`-এর largest" খুঁজে সেটা মুছে ফেলা — এটাই predecessor + delete।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **ordered multiset** — দাম duplicate হতে পারে বলে multiset। Python-এ সরাসরি balanced-BST নেই; দুটো সহজ পথ: (a) দাম sort করে একটা list রেখে `bisect`-এ predecessor খুঁজে index-টা remove করা, অথবা (b) `sortedcontainers.SortedList`। নিচে standard-library `bisect` ব্যবহার করেছি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি customer-এ দরকার "`<= max_price`-এর largest" — heap-এর global max এখানে কাজ করে না, কারণ bound প্রতিবার আলাদা। sorted order-এ `bisect_right(prices, max_price) - 1` ঠিক সেই index দেয় O(log n)-এ; তারপর remove। (`SortedList` হলে remove-ও O(log n); plain list থেকে remove O(n), তবে CSES-এর সরল ব্যাখ্যার জন্য তা যথেষ্ট স্পষ্ট।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা customer-এর জন্য পুরো বাকি ticket-list **scan** করে `<= max_price` দামগুলোর মধ্যে largest খুঁজে নাও, সেটা remove করো, না পেলে -1।
```text
প্রতি customer -> পুরো list ঘেঁটে best <= budget খোঁজো -> remove -> পরের customer
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি customer-এ পুরো list scan মানে O(n), customer m-টা — মোট **O(n·m)**। CSES-এ n, m ≈ 2·10⁵ হলে এটা ~4·10¹⁰ operation, সহজেই TLE। অথচ "`<= x`-এর largest" একটা sorted structure-এ O(log n)-এই পাওয়া যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: প্রশ্নটা আসলে repeated **predecessor query + delete**। দাম একবার sort করে রাখলে, প্রতিটা customer-এর উত্তর `bisect_right(prices, budget) - 1` index-এ; সেই index ≥ 0 হলে ওই দাম দাও আর মুছে দাও, নাহলে -1। Global max heap এখানে যথেষ্ট নয় কারণ bound প্রতিবার বদলায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দাম sort করো একটা list-এ। প্রতিটা customer-এর জন্য `bisect_right(prices, budget)` দিয়ে "budget-এর চেয়ে বড় প্রথম position" পাও; তার এক আগেরটা (`idx-1`) হলো `<= budget`-এর largest। `idx-1 >= 0` হলে answer = `prices[idx-1]`, list থেকে সেই index pop করো; নাহলে answer -1। (Production-এ `SortedList` দিয়ে remove-ও O(log n) করা যায়।)
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "ticket বেচা" না ভেবে ভাবো "একটা ordered multiset-এ বারবার `floor(x)` (x-এর `<=` largest) query করছি আর সেই element মুছছি।" "best price ≤ budget তারপর remove / ordered set / predecessor" — এমন কথা শুনলেই balanced ordered structure (বা sort + bisect)-এর কথা মাথায় আসা উচিত; plain heap এখানে কম পড়বে।
### ছবিতে বোঝা {#7-visual-explanation}
`tickets = [5,3,7,8,5]`, customers = `[4,8,3]` — দাম sort করি, প্রতি customer-এ `<= budget`-এর largest নিই আর মুছি:
```text
sorted prices: [3, 5, 5, 7, 8]
customer 4: <=4 largest = 3 -> দেয় 3, মুছি prices [5, 5, 7, 8]
customer 8: <=8 largest = 8 -> দেয় 8, মুছি prices [5, 5, 7]
customer 3: <=3 largest = নেই -> দেয় -1 prices [5, 5, 7]
answers: [3, 8, -1]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `tickets=[1,1,1]`, customers=`[1,1,1,1]`:
1. sorted prices = `[1, 1, 1]`, answers = []
2. customer 1: `bisect_right([1,1,1], 1) = 3` → idx-1 = 2 ≥ 0 → answer 1, pop index 2 → prices `[1,1]`
3. customer 1: `bisect_right([1,1], 1) = 2` → idx-1 = 1 → answer 1, pop index 1 → prices `[1]`
4. customer 1: `bisect_right([1], 1) = 1` → idx-1 = 0 → answer 1, pop index 0 → prices `[]`
5. customer 1: `bisect_right([], 1) = 0` → idx-1 = −1 < 0 → answer −1
6. return [1, 1, 1, −1]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import bisect
def concert_tickets(tickets, customers):
prices = sorted(tickets) # ordered multiset (sorted list)
answers = []
for budget in customers:
# budget-এর <= largest দামের index = bisect_right - 1
idx = bisect.bisect_right(prices, budget) - 1
if idx >= 0:
answers.append(prices[idx])
prices.pop(idx) # সেই ticket বিক্রি -> remove
else:
answers.append(-1) # বাজেটের মধ্যে কিছু নেই
return answers
# ---- tests ----
assert concert_tickets([5, 3, 7, 8, 5], [4, 8, 3]) == [3, 8, -1]
assert concert_tickets([2], [1]) == [-1] # বাজেট কম
assert concert_tickets([2], [2]) == [2] # ঠিক bound
assert concert_tickets([1, 1, 1], [1, 1, 1, 1]) == [1, 1, 1, -1] # stock শেষ
assert concert_tickets([10, 20, 30], [25, 25, 25]) == [20, 10, -1] # বড়টা আগে যায়
assert concert_tickets([], [5, 6]) == [-1, -1] # ticket নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `prices = sorted(tickets)` — দামগুলোকে ছোট-থেকে-বড় সাজানো ordered multiset বানায়।
- `for budget in customers:` — customer-রা যে order-এ আসে সেই order-এই process।
- `idx = bisect.bisect_right(prices, budget) - 1` — `budget`-এর চেয়ে বড় প্রথম position-এর ঠিক আগেরটা = `<= budget`-এর largest-এর index।
- `if idx >= 0:` — অমন একটা ticket আছে কিনা; না থাকলে idx হবে −1।
- `answers.append(prices[idx]); prices.pop(idx)` — সেই দাম record করো আর ticket-টা remove (বিক্রি হয়ে গেল)।
- `else: answers.append(-1)` — বাজেটের মধ্যে কিছু নেই, customer কিছু কেনে না।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`concert_tickets([1,1,1], [1,1,1,1])` section 14-এর dry run মেনে [1,1,1,−1] দেয় — চতুর্থ জন stock শেষ পায়। main example [3,8,−1]; `[10,20,30]` বাজেট 25-এ আগে 20 তারপর 10, শেষে −1; খালি ticket-list-এ সব −1। output প্রতিটা customer-এর নির্দিষ্ট ক্রমে, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O((n + m) log n)** আদর্শ ordered-multiset (যেমন `SortedList`)-এ — sort O(n log n), প্রতি customer query+delete O(log n)। নিচের সরল version-এ `list.pop(idx)` O(n) বলে worst case O(n·m); ব্যাখ্যা স্পষ্ট রাখতে এটা রাখা হয়েছে, কিন্তু বড় input-এ `SortedList` ব্যবহার করো।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — sorted prices list, আর O(m) output। সব মিলিয়ে input-এর সমানুপাতিক।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `bisect_left` ব্যবহার করা যেখানে `bisect_right` দরকার — তখন budget-এর সমান দামের ticket miss হতে পারে।
- remove করতে ভুলে যাওয়া — তাহলে একই ticket একাধিক customer-কে বিক্রি হয়ে যায়।
- বড় input-এ plain-list `pop(idx)`-এর O(n) cost ভুলে যাওয়া — TLE; তখন `SortedList`/BIT দরকার।
- empty list-এ `idx-1 = -1` কে valid index ভাবা — Python-এ `prices[-1]` ভুল element দেবে; তাই `idx >= 0` guard জরুরি।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `05-hashing`/sorted-structures-এর ordered-collection ধারণা — predecessor query + delete। আর `08`-এর heap-ধারণার সীমা চেনায়: heap শুধু global extreme দেয়, "একটা bound-এর নিচে best" দিতে পারে না; তখন balanced ordered structure লাগে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Towers (CSES) —