लोगों की शफ़ल्ड कतार को पुनर्प्राप्त करने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है जहां प्रत्येक पंक्ति में दो मान [height, count] होते हैं जो दर्शाते हैं कि व्यक्ति की दी गई ऊंचाई है और उसके सामने 'count' संख्या में लोग हैं जो कम से कम उतने ही लंबे हैं। अब विचार करें कि यह कतार शफ़ल हो गई है, हमें कतार का मूल क्रम पुनर्प्राप्त करना है।

उदाहरण के लिए, यदि इनपुट इस तरह है:

तो आउटपुट होगा:

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

• N := मैट्रिक्स की पंक्ति संख्या
• मैट्रिक्स पंक्तियों को बढ़ती ऊंचाई और घटते काउंट के आधार पर पुनर्व्यवस्थित करें
• ans := आकार N की एक सूची बनाएं और प्रारंभ में सभी प्रविष्टियां नल हैं
• प्रत्येक ऊंचाई h, और काउंट c के लिए मैट्रिक्स पंक्ति में, करें
  • temp := 0
  • प्रत्येक इंडेक्स i, और मान num ans के लिए, करें
    • यदि temp >= c और num नल है, तो
      • ans[i] := [h, c]
      • लूप से बाहर निकलें
    • यदि num नल है या num[0] >= h, तो
      • temp := temp + 1
• ans लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, matrix):
        N = len(matrix)
        matrix.sort(key=lambda x: [x[0], -x[1]])
        ans = [None] * N
        for h, c in matrix:
            temp = 0
            for i, num in enumerate(ans):
                if temp >= c and num is None:
                    ans[i] = [h, c]
                    break
                if num is None or num[0] >= h:
                    temp += 1
        return ans

ob = Solution()
matrix = [
    [2, 2],
    [4, 0],
    [5, 0]
]
print(ob.solve(matrix))

इनपुट

[[2, 2], [4, 0], [5, 0]]

आउटपुट

[[4, 0], [5, 0], [2, 2]]