Skip to content

015 — Concert Tickets

Source

  • Original source: CSES Sorting and Searching — ordered-multiset query
  • Platform: CSES Problem Set — https://cses.fi/problemset/ ("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

1. Problem in simple words

n-টা concert ticket আছে, প্রতিটার একটা দাম। m-জন customer আসে এক এক করে; প্রত্যেকের একটা সর্বোচ্চ বাজেট max_price। প্রতিটা customer তার বাজেটের মধ্যে যে ticket-টার দাম সবচেয়ে বেশি (অর্থাৎ <= max_price-এর মধ্যে largest) সেটা কেনে, আর সেই ticket চলে যায়। বাজেটের মধ্যে কোনো ticket না থাকলে সে কিছু কেনে না। প্রতিটা customer কত দাম দিল (বা না কিনলে -1) সেটা order-এ return করো।

tickets = [5, 3, 7, 8, 5], customers = [4, 8, 3]  ->  [3, 8, -1]

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-এর সরল ব্যাখ্যার জন্য তা যথেষ্ট স্পষ্ট।)

6. Real-life analogy

ভাবো একটা দোকানে নানা দামের ticket তাকে সাজানো — সস্তা থেকে দামি। একজন ক্রেতা এসে বলে "আমার বাজেট 4"; বিক্রেতা তাকের যে ticket-গুলো 4-এর মধ্যে, তাদের মধ্যে সবচেয়ে দামিটা তুলে দেন, সেটা তাক থেকে সরে যায়। বাজেটের নিচে কিছু না থাকলে খালি হাতে ফেরত। "এই দামের নিচে সবচেয়ে দামিটা চট করে দাও আর সরিয়ে নাও" — সেই sorted তাকটাই ordered multiset।

7. Visual explanation

tickets = [5,3,7,8,5], customers = [4,8,3] — দাম sort করি, প্রতি customer-এ <= budget-এর largest নিই আর মুছি:

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]

8. Example input and output

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 শেষ)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা customer-এর জন্য পুরো বাকি ticket-list scan করে <= max_price দামগুলোর মধ্যে largest খুঁজে নাও, সেটা remove করো, না পেলে -1।

প্রতি 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 এখানে কম পড়বে।

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]

15. Python solution

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 কিছু কেনে না।

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!।

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 জরুরি।

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

23. Pattern learned

Ordered multiset query: যখন বারবার "একটা bound-এর <=/>= best element নাও আর মুছে ফেলো" লাগে, তখন heap যথেষ্ট নয় — একটা balanced ordered structure (বা sort + bisect) দরকার, যেটা predecessor/successor query আর delete দুটোই O(log n)-এ দেয়।

24. Final summary

ভবিষ্যতের আমাকে: "প্রতি customer তার বাজেটের নিচের সবচেয়ে দামি ticket নেয়, ticket সরে যায়" = ordered multiset-এ bisect_right - 1 predecessor + delete। ছোট input-এ sort+list চলে, বড়তে SortedList/BIT। মনে রেখো — plain heap এখানে কম পড়ে, কারণ bound প্রতিবার বদলায়।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।