पायथन में दी गई शर्तों के साथ संसाधित किए जाने वाले अनुरोधों की संख्या की जांच करने का कार्यक्रम

मान लीजिए कि हमारे पास अनुरोधों की एक सूची है जहां प्रत्येक सूची में [यूआईडी, टाइम_सेक] जैसे तत्व शामिल हैं (यूआईडी यूजर आईडी है और टाइम_सेक टाइमस्टैम्प है)। यह इंगित करता है कि जिस उपयोगकर्ता की आईडी uid है, उसने टाइमस्टैम्प time_sec पर एक वेबसाइट से अनुरोध किया है। हमारे पास दो मान u और g भी हैं जहां u किसी दिए गए uid के लिए किसी भी <60 सेकंड के फ्रेम में अनुमत अनुरोधों की अधिकतम संख्या को दर्शाता है और g वैश्विक स्तर पर किसी भी <60 सेकंड के फ्रेम में अनुमत अनुरोधों की अधिकतम संख्या है। अब यदि हम प्रत्येक अनुरोध को एक-एक करके संसाधित करना चाहते हैं और उन्हें दर सीमित करना चाहते हैं। और अगर एक ही समय में कई उपयोगकर्ताओं द्वारा अनुरोध किया जाता है, तो कम यूआईडी वाले अनुरोधों को पहले संसाधित किया जाएगा, अन्यथा उस अनुरोध को छोड़ दिया जाएगा। हमें उन अनुरोधों की कुल संख्या का पता लगाना होगा जिन्हें सफलतापूर्वक संसाधित किया जाएगा।

इसलिए, यदि इनपुट अनुरोधों की तरह है =[[0, 1], [1, 2], [1,3]] u =1 g =5, तो आउटपुट 2 होगा, जैसा कि उपयोगकर्ता 0 और 1 भेज सकते हैं समय 1 और 2, लेकिन उपयोगकर्ता 1 से दूसरा अनुरोध संसाधित नहीं किया जाएगा क्योंकि एक उपयोगकर्ता 60 सेकंड के फ्रेम में अधिकतम 1 अनुरोध भेज सकता है।

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

• अंतिम:=एक खाली नक्शा
• कुल :=खाली डबल एंडेड कतार
• विंडोटाइम:=60
• समय के आधार पर अनुरोधों को क्रमबद्ध करें, यदि वे समान हैं तो यूआईडी के आधार पर क्रमबद्ध करें
• राशि :=0
• अनुरोध में प्रत्येक r के लिए, करें
  • [यूआईडी, समय] :=आर
  • जबकि कुल का आकार> 0 और कुल[0] + विंडोटाइम <=समय, करें
    • कुल का बायां आइटम हटाएं
  • आखिरी का आकार [यूआईडी]> 0 और आखिरी [यूआईडी, 0] + विंडोटाइम <=समय, करते हैं
    • पिछली[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