पायथन में प्रश्नों से निकटतम कमरा खोजने का कार्यक्रम

मान लीजिए कि कमरे नामक एक सरणी है। जहां कमरे [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 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

आकार के आधार पर कमरों को छाँटें, जब आकार समान हो तो कमरे की आईडी के आधार पर
query =युग्मों की सूची (qid, size, i) अनुक्रमणिका i के लिए, और युग्म (qid, size) प्रश्नों में
आकार के आधार पर प्रश्नों को उल्टे क्रम में क्रमबद्ध करें, यदि आकार समान हैं, तो पसंदीदा के आधार पर, जब दोनों समान हों तो अनुक्रमणिका के आधार पर
उत्तर:=प्रश्नों के आकार के समान आकार की एक सरणी और -1 से भरें
एक्स:=एक नई सूची
प्रश्नों में प्रत्येक (qid, आकार, i) के लिए, करें
- जबकि कमरे और कमरों के अंतिम आइटम का आकार>=आकार, करते हैं
  - (idr, p) :=कमरों से अंतिम तत्व हटा दिया गया
  - Idr डालने के बाद X को सॉर्ट करें
- अगर X खाली नहीं है, तो
  - j :=अनुक्रमणिका जहाँ X क्रमित रहने के लिए qid सम्मिलित करना है
  - यदि j, X के आकार के समान है, तो
    - ans[i] :=X का अंतिम तत्व
  - अन्यथा जब j, 0 के समान हो, तब
    - ans[i] :=X[0]
  - अन्यथा,
    - अगर X[j] - qid
      - Ans[i] :=X[j]
    - अन्यथा,
      - ans[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]