โปรแกรมหาห้องที่ใกล้เคียงที่สุดจากการสอบถามใน Python

สมมติว่ามีอาร์เรย์ที่เรียกว่าห้อง โดยที่ rooms[i] มีคู่ [roomId_i, size_i] หมายถึงห้องที่มี ID คือ roomId_i และขนาดคือ size_i หมายเลขห้องทั้งหมดแตกต่างกัน เรายังมีการสืบค้นอาร์เรย์อื่น โดยที่การสืบค้น[j]มีคู่ [preferred_j, minSize_j] คำตอบของคำถามข้อที่ j คือรหัสห้องของห้องนั้นๆ −

• ห้องมีขนาดอย่างน้อย minSize_j และ

• |id - ที่ต้องการ_j| ถูกย่อให้เล็กสุด

ทีนี้ ถ้ามีความเสมอภาคในความแตกต่าง ให้ใช้ห้องที่มีรหัสที่เล็กที่สุด หากไม่มีห้องดังกล่าว ให้คืนค่า -1 ดังนั้นเราจึงต้องหาอาร์เรย์ที่เรียกว่า คำตอบ ซึ่งมีความยาวเท่ากับข้อความค้นหา ซึ่งประกอบด้วยคำตอบของข้อความค้นหาที่ j

ดังนั้น ถ้าอินพุตเป็นเหมือนห้อง =[[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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• จัดเรียงห้องตามขนาด เมื่อขนาดเท่ากัน ให้เรียงตามรหัสห้อง

• แบบสอบถาม =รายการของคู่ (qid,ขนาด,i) สำหรับดัชนี i และคู่ (qid, ขนาด) ในแบบสอบถาม

• จัดเรียงคำค้นหาในลำดับย้อนกลับตามขนาด หากขนาดเท่ากัน ให้จัดเรียงตามที่ต้องการ เมื่อทั้งคู่เหมือนกันแล้วจึงอิงตามดัชนี

• ans :=อาร์เรย์ที่มีขนาดเท่ากับขนาดของข้อความค้นหาและเติมด้วย -1

• X :=รายการใหม่

• สำหรับแต่ละ (qid, size, i) ในแบบสอบถาม ทำ

  • ในขณะที่ห้องและขนาดของห้องสุดท้าย>=ขนาดทำ

    • (idr, p) :=ลบองค์ประกอบสุดท้ายออกจากห้อง

    • เรียงลำดับ X หลังจากใส่ idr

  • ถ้า X ไม่ว่างก็

    • j :=ดัชนีตำแหน่งที่จะแทรก qid เพื่อให้ X เรียงลำดับอยู่

    • ถ้า 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]