सभी फिल्में देखें एल्गोरिदम

Question

मैं इस समस्या को पूरा करता हूं जो बहुत दिलचस्प लगता है। कुछ फिल्मों है कि हम उन सभी को देखना चाहते हैं लेकिन वे केवल निम्नलिखित समय पर दिखाने:

movieA : 15 
movieB : 14, 15, 17 
movieC : 15, 17 
movieD : 15, 20 

हम एक 15 में 14 में सी 17 और डी 20 में देख सकते हैं, बी,, तो यह है उन सभी को देखने के लिए संभव है। ध्यान दें कि आप 15 पर सी नहीं देख सकते हैं, व्यवहार्य नहीं।

जैसा आपने अनुमान लगाया है, यह है कि हम उन्हें सभी देख सकते हैं या नहीं।

स्पष्ट रूप से हम इसे सभी संभावनाओं का प्रयास करके बैकट्रैकिंग के साथ हल कर सकते हैं। क्या ऐसा करने का कोई बेहतर तरीका है? मेरे पास पहले से कम से कम उपलब्ध समय के साथ फिल्मों के साथ शुरू करने का विचार है, इस तरह समाधान होने पर हम समाधान को तेजी से पा सकते हैं, सबसे खराब केस टाइम जटिलता अभी भी वही है।

क्या इस समस्या के लिए वहां कोई बेहतर एल्गोरिदम है?

पीएस जैसा कि @gen ने पूछा, मैं यह इंगित करना भूल गया कि प्रत्येक फिल्म 1 घंटा है, इसलिए यदि आप 14:00 बजे एक देखते हैं, तो आप 15:00 बजे किसी को याद नहीं करेंगे। पूछने के लिए धन्यवाद।

Answer 1

फिल्मों की संख्या और प्रत्येक फिल्म के लिए संभावित अलग-अलग समय की संख्या पर सीमाओं के आधार पर, आप एक तरफ फिल्मों के साथ एक द्विपक्षीय ग्राफ बना सकते हैं और दूसरी तरफ के समय और दूसरे प्रवाह के समय निर्धारित करने के लिए अधिकतम प्रवाह एल्गोरिदम चला सकते हैं अधिकतम मिलान यदि फिल्म i को j पर देखा जा सकता है, तो ग्राफ़ में संबंधित नोड्स के बीच एक किनारे जोड़ें।

Answer 2

WHILE list of movie times isn't empty 
    1. Sort movie showtime list in order of the number of showtimes. 
    2. Watch next movie according to this sort at the first available time. 
    3. Remove respective time from each movie showtime list and movie 
     from the movie list. 

अजगर प्रयास:

A=[15,'A'] 
B=[14,15,17,'B'] 
C=[15,17,'C'] 
D=[15,20,'D'] 

movies=[A,B,C,D] 


watchOrder = [] 

def f(x): 
    while x: # while x isnt empty 
     x=sorted(x, key=len) 
     watchOrder.append(x[0]) 
     r = x[0][0] 
     x.remove(x[0]) 
     for l in x: 
      if r in l: 
       l.remove(r) 
f(movies) 
print(watchOrder) 

Answer 3

एक द्विपक्षीय ग्राफ पर एक अधिकतम मिलान समस्या की तरह लग रहा। ग्राफ के शिखर दो स्वतंत्र सेट 'दिन के घंटे' और 'फिल्म शीर्षक' हैं। ग्राफ के किनारे किसी विशेष समय के किसी विशेष फिल्म के प्रदर्शन होते हैं।

स्टीवन स्कीएना के एल्गोरिदम डिजाइन मैनुअल के अनुसार, सबसे अच्छा ज्ञात एल्गोरिदम हॉपक्रॉफ्ट-कार्प एल्गोरिदम है जो ओ (ई * एसकर्ट (वी)) में चलता है। ई किनारों की संख्या है, यानी। शो की संख्या। वी शिखर की संख्या है, यानी। फिल्मों की संख्या और अलग-अलग घंटों की संख्या जिसके दौरान फिल्मों को दिखाया जाता है। अपने उदाहरण में, ई = 8 के प्रदर्शनों, वी = 4 फिल्मों 4 अलग बार = 8.

https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

नोट मिलान निर्माण तभी संभव है, क्योंकि आपके फिल्मों सभी घंटे से शुरू होकर वास्तव में एक घंटे तक। वे या तो बिल्कुल मेल खाते हैं, या बिल्कुल ओवरलैप नहीं करते हैं।