โปรแกรมตรวจสอบจำนวนคำขอที่จะดำเนินการตามเงื่อนไขที่กำหนดใน python

สมมติว่าเรามีรายการคำขอที่แต่ละรายการมีองค์ประกอบเช่น [uid, time_sec] (uid คือรหัสผู้ใช้และ time_sec คือการประทับเวลา) สิ่งนี้บ่งชี้ว่าผู้ใช้ที่มี id เป็น uid ได้ร้องขอไปยังเว็บไซต์ ณ เวลาประทับ time_sec นอกจากนี้เรายังมีค่าสองค่า u และ g โดยที่ u หมายถึงจำนวนคำขอสูงสุดที่อนุญาตในเฟรม <60 วินาทีสำหรับ uid ที่กำหนด และ g คือจำนวนคำขอสูงสุดที่อนุญาตในเฟรม <60 วินาทีทั่วโลก ตอนนี้ถ้าเราต้องการประมวลผลคำขอทีละรายการและจำกัดอัตรา และหากมีคำขอพร้อมกันโดยผู้ใช้หลายคน คำขอที่มี uid ต่ำกว่าจะได้รับการประมวลผลก่อน มิฉะนั้น คำขอนั้นจะถูกยกเลิก เราต้องหาจำนวนคำขอทั้งหมดที่จะดำเนินการได้สำเร็จ

ดังนั้น หากอินพุตเหมือนกับการร้องขอ =[[0, 1],[1, 2],[1,3]] u =1 g =5 ผลลัพธ์จะเป็น 2 เนื่องจากผู้ใช้ 0 และ 1 สามารถส่งได้ที่ เวลา 1 และ 2 แต่คำขอที่สองจากผู้ใช้ 1 จะไม่ถูกประมวลผลเนื่องจากผู้ใช้รายหนึ่งสามารถส่งคำขอได้ไม่เกิน 1 คำขอใน 60 วินาทีเฟรม

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

• สุดท้าย :=แผนที่ว่างเปล่า
• รวม :=คิวสิ้นสุดคู่ที่ว่างเปล่า
• เวลาหน้าต่าง :=60
• จัดเรียงคำขอตามเวลา หากเหมือนกันก็จัดเรียงตาม uid
• จำนวนเงิน :=0
• สำหรับแต่ละ r ในการร้องขอ ทำ
  • [uid, เวลา] :=r
  • ในขณะที่ขนาดรวม> 0 และรวม[0] + windowtime <=เวลา ทำ
    • ลบรายการด้านซ้ายของยอดทั้งหมด
  • ในขณะที่ขนาดของ last[uid]> 0 และ last[uid, 0] + windowtime <=time, do
    • ลบรายการด้านซ้ายจาก Last[uid]
  • ถ้าขนาดรวม
  • ใส่เวลาที่ท้าย[uid]สุดท้าย
  • ใส่เวลาที่ท้ายยอดทั้งหมด
  • จำนวนเงิน :=จำนวน + 1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

from collections import defaultdict, deque
class Solution:
   def solve(self, requests, u, g):
      last = defaultdict(deque)
      total = deque()

      windowtime = 60
      requests.sort(key=lambda x: [x[1], x[0]])

      amount = 0
      for r in requests:
         uid, time = r

         while len(total) > 0 and total[0] + windowtime <= time:
            total.popleft()

         while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
            last[uid].popleft()

         if len(total) < g and len(last[uid]) < u:
            last[uid].append(time)
            total.append(time)
            amount += 1
      return amount
     
ob = Solution()
requests = [[0, 1],[1, 2],[1,3]]
u = 1
g = 5
print(ob.solve(requests, u, g))

อินพุต

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

ผลลัพธ์

2