पायथन में जांचें कि क्या सभी को सीट मिल सकती है या नहीं

मान लीजिए हमारे पास एक संख्या n है, जहां n लोग सीट खोज रहे हैं। हमारे पास बिट्स की एक सूची भी है जहां 1 पहले से भरी हुई सीट को दर्शाता है और 0 खाली सीट को। कोई भी दो लोग एक-दूसरे के बगल में नहीं बैठ सकते, इसलिए हमें जांचना होगा कि क्या सभी n लोगों को सीट मिल सकती है या नहीं।

उदाहरण के लिए, यदि इनपुट है n = 2 और seats = [1, 0, 0, 0, 1, 0, 0], तो आउटपुट True होगा, क्योंकि वे इंडेक्स 2 और 6 पर बैठ सकते हैं।

समाधान दृष्टिकोण

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

• seats सूची की शुरुआत में 0 जोड़ें और अंत में [0, 1] जोड़ें
• res := 0, gap := 0 इनिशियलाइज़ करें
• seats में प्रत्येक तत्व i के लिए लूप चलाएं:
  • यदि i 0 के बराबर है, तो gap को 1 से बढ़ाएं
  • अन्यथा जब gap > 0 हो, तो:
    • res में (gap - 1) // 2 का फ्लोर मान जोड़ें
    • gap को 0 पर रीसेट करें
• यदि res >= n तो True लौटाएं, अन्यथा False

उदाहरण कोड

def solve(n, seats):
    seats = [0] + seats + [0, 1]
    res = 0
    gap = 0
    for i in seats:
        if i == 0:
            gap += 1
        elif gap > 0:
            res += (gap - 1) // 2
            gap = 0
    return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

इनपुट

2, [1, 0, 0, 0, 1, 0, 0]

आउटपुट

True