पायथन में जांचें कि सभी लोग दो मशीनों पर वोट दे सकते हैं या नहीं

मान लीजिए हमारे पास n लोग हैं और दो समान वोटिंग मशीनें हैं। हमारे पास आकार n का एक ऐरे time है जहां time[i] i-वें व्यक्ति द्वारा किसी भी मशीन पर वोट देने में खर्च किया गया कुल समय दर्शाता है। एक समय में प्रत्येक मशीन पर केवल एक व्यक्ति हो सकता है। हमारे पास एक मान x भी है जो मशीनों के संचालन के लिए अधिकतम स्वीकार्य समय दर्शाता है। हमें यह जांचना है कि क्या सभी व्यक्ति अपना वोट दे सकते हैं या नहीं।

उदाहरण के लिए, यदि इनपुट n = 3, x = 7, time = [3, 5, 3] है, तो आउटपुट True होगा। क्योंकि समय t0 पर 0-वां व्यक्ति पहली मशीन पर जाता है और 1-वां व्यक्ति दूसरी मशीन पर। अब समय t3 पर पहली मशीन खाली होती है। अब 2-वां व्यक्ति पहली मशीन पर जाता है और समय t5 पर दूसरी मशीन खाली होती है और समय t6 पर पहली मशीन खाली होती है, इसलिए सभी प्रतिभागियों ने समय पर वोट दे दिया।

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

हम प्रीफिक्स योग (prefix sum) का उपयोग करके सभी संभावित विभाजनों की जांच करते हैं कि क्या दोनों मशीनों पर समय x के भीतर पूरा हो सकता है।

एल्गोरिदम चरण:

1. total_sum = sum(time) की गणना करें
2. यदि total_sum <= x, तो True लौटाएं (एक मशीन ही काफी है)
3. time को सॉर्ट करें
4. प्रीफिक्स योग ऐरे prev_sum बनाएं
5. सभी संभावित जोड़े (i, j) के लिए जहां i < j:
• temp_sum = prev_sum[i] + (total_sum - prev_sum[j]) की गणना करें
• यदि temp_sum <= x और total_sum - temp_sum <= x, तो True लौटाएं
6. False लौटाएं

पायथन कार्यान्वयन

def solve(n, x, time):
    total_sum = sum(time)
    if total_sum <= x:
        return True
    
    time.sort()
    prev_sum = [0] * len(time)
    prev_sum[0] = time[0]
    for i in range(1, len(prev_sum)):
        prev_sum[i] = prev_sum[i-1] + time[i]
    
    for i in range(len(prev_sum)):
        for j in range(i + 1, len(prev_sum)):
            temp_sum = prev_sum[i] + (total_sum - prev_sum[j])
            if temp_sum <= x and total_sum - temp_sum <= x:
                return True
    return False

n = 3
x = 7
time = [3, 5, 3]
print(solve(n, x, time))  # True

इनपुट

3, 7, [3, 5, 3]

आउटपुट

True

व्याख्या:

सॉर्टेड time = [3, 3, 5], कुल योग = 11।

मशीन 1: 3 + 3 = 6 ≤ 7 ✓

मशीन 2: 5 ≤ 7 ✓

दोनों मशीनें समय सीमा के भीतर काम पूरा करती हैं।