পাইথনে কোয়েরি থেকে নিকটতম রুম খুঁজে বের করার প্রোগ্রাম

ধরুন রুম নামক একটি অ্যারে আছে। যেখানে রুম[i] একটি জোড়া রয়েছে [roomId_i, size_i] এমন একটি ঘরকে বোঝায় যার আইডি হল roomId_i এবং সাইজ হল size_i। সমস্ত রুম নম্বর স্বতন্ত্র. আমাদের আরও একটি অ্যারে কোয়েরি আছে, যেখানে ক্যোয়ারী [j] একটি জোড়া [preferred_j, minSize_j] ধারণ করে। jth প্রশ্নের উত্তর হল একটি ঘরের রুম নম্বর আইডি যেমন −

• রুমটির আকার কমপক্ষে minSize_j, এবং

• |আইডি - পছন্দের_জে| মিনিমাইজ করা হয়।

এখন, যদি পরম পার্থক্য একটি টাই হয়, তারপর সবচেয়ে ছোট আইডি সঙ্গে ঘর ব্যবহার করুন. যদি এমন কোন রুম না থাকে তবে -1 ফিরে আসুন। তাই আমাদের উত্তর নামক একটি অ্যারে খুঁজে বের করতে হবে যার দৈর্ঘ্য কোয়েরির সমান, যেটিতে jth কোয়েরির উত্তর রয়েছে।

সুতরাং, যদি ইনপুটটি ঘরের মত হয় =[[2,2],[1,2],[3,2]] প্রশ্ন =[[3,1],[3,3],[5,2]], তাহলে আউটপুট হবে [3, -1, 3] কারণ

• প্রশ্নের জন্য [3,1]:ঘর 3 সবচেয়ে কাছের কারণ |3 - 3| =0, এবং 2 এর আকার কমপক্ষে 1, তাই উত্তরটি 3।

• প্রশ্নের জন্য [3,3]:এমন কোনো ঘর নেই যার আকার কমপক্ষে 3, তাই উত্তর হল -1।

• প্রশ্নের জন্য [5,2]:ঘর 3 সবচেয়ে কাছের কারণ |3 - 5| =2, এবং 2 এর আকার কমপক্ষে 2, তাই উত্তরটি 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• আকারের উপর ভিত্তি করে ঘর সাজান, যখন আকার একই হয় তখন রুম আইডির উপর ভিত্তি করে

• প্রশ্ন =সূচক i-এর জন্য জোড়ার একটি তালিকা (qid,size,i), এবং প্রশ্নগুলিতে জোড়া (qid, আকার)

• প্রশ্নগুলিকে আকারের উপর ভিত্তি করে বিপরীত ক্রমে সাজান, যদি আকার একই হয়, তাহলে পছন্দের উপর ভিত্তি করে, যখন উভয়ই একই হয় তখন সূচকের উপর ভিত্তি করে

• উত্তর :=প্রশ্নের আকারের সমান আকারের একটি অ্যারে এবং -1 দিয়ে পূরণ করুন

• X :=একটি নতুন তালিকা

• প্রশ্নে প্রতিটি (qid, আকার, i) জন্য, করুন

  • যখন কক্ষ এবং কক্ষের শেষ আইটেমের আকার>=আকার, করুন

    • (idr, p) :=রুম থেকে শেষ উপাদান মুছে ফেলা হয়েছে

    • idr ঢোকানোর পরে X সাজান

  • যদি X খালি না হয়, তাহলে

    • j :=সূচী যেখানে X সাজানো থাকার জন্য qid ঢোকাতে হবে

    • যদি j X এর আকারের সমান হয়, তাহলে

      • ans[i] :=X

        এর শেষ উপাদান

    • অন্যথায় যখন j 0 এর মত হয়, তখন

      • উত্তর[i] :=X[0]

    • অন্যথায়,

      • যদি X[j] - qid

        • উত্তর[i] :=X[j]

      • অন্যথায়,

        • উত্তর[i] :=X[j-1]

• উত্তর ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

import bisect
def solve(rooms, queries):
   rooms.sort(key = lambda x: (x[1], x[0]))
   queries = [(qid,size,i) for i, (qid, size) in enumerate(queries)]
   queries.sort(key = lambda x: (x[1], x[0], x[2]), reverse = True)
   ans = [-1] * len(queries)
   X = []
   for qid, size, i in queries:
      while rooms and rooms[-1][1] >= size:
         idr, _ = rooms.pop()
         bisect.insort(X, idr)
      if X:
         j = bisect.bisect(X, qid)
         if j == len(X):
            ans[i] = X[-1]
         elif j == 0:
            ans[i] = X[0]
         else:
            if X[j] - qid < qid - X[j-1]:
               ans[i] = X[j]
            else:
               ans[i] = X[j-1]
   return ans

rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))

ইনপুট

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]

আউটপুট

[3, -1, 3]