एल्गोरिथम समस्याओं का समाधान: होटल बुक करने की संभावना

आलेख का अनुवाद विशेष रूप से "डेवलपर्स के लिए एल्गोरिदम" पाठ्यक्रम के छात्रों के लिए तैयार किया गया था।



यह आलेख एल्गोरिदम समस्याओं को हल करने के तरीके पर एक श्रृंखला का हिस्सा है। अपने व्यक्तिगत अनुभव के आधार पर, मैंने पाया कि अधिकांश संसाधन समाधान का विस्तार से वर्णन करते हैं। तर्क की मुख्य पंक्ति का स्पष्टीकरण जो एक प्रभावी समाधान खोजने की अनुमति देता है, दुर्भाग्य से, बहुत आम नहीं है। इसलिए, इस श्रृंखला का लक्ष्य खरोंच से समस्याओं को हल करने के लिए तर्क के संभावित पाठ्यक्रम का वर्णन करना है।

---

कार्य

• कार्य: साक्षात्कार

होटल प्रबंधक को अगले सीज़न के लिए एन आरक्षण आदेशों को संसाधित करना होगा। उनके होटल में K कमरे हैं। बुकिंग की जानकारी में चेक-इन की तारीख और चेक-आउट की तारीख होती है। प्रबंधक यह पता लगाना चाहते हैं कि क्या मांग को पूरा करने के लिए होटल में पर्याप्त कमरे हैं।

इनपुट डेटा:

- आगमन के समय के बारे में जानकारी के साथ एक सूची में प्रवेश करने वाला पहला
- दूसरा - प्रस्थान के समय की जानकारी के साथ एक सूची
- तीसरा - के, कमरों की संख्या का संकेत

आउटपुट डेटा:
- एक तार्किक मूल्य जो कमरे बुक करने की क्षमता को इंगित करता है
झूठ का मतलब है कि होटल में एन बुकिंग के लिए पर्याप्त जगह नहीं है
यह सच है कि होटल में एन बुकिंग के लिए पर्याप्त कमरे हैं

एक उदाहरण:

इनपुट डेटा:
- चेक-इन = [1, 3, 5]
- प्रस्थान = [२, ६, १०]
- के = १

आउटपुट: झूठा। दिन = 5 पर होटल में 2 मेहमान हैं। लेकिन हमारे पास केवल एक संख्या है।

• श्रेणी: एरे

निर्णय प्रक्रिया

यह कार्य दिलचस्प है, मेरी राय में, क्योंकि इसे हल करने के कई अलग-अलग तरीके हैं। आइए विकल्पों को देखें।

एक संरचना जो प्रत्येक दिन काउंटरों को संग्रहीत करती है
पहला विचार यह हो सकता है कि हमें प्रत्येक दिन के लिए ऑर्डर की संख्या को संग्रहीत करने के लिए एक संरचना की आवश्यकता है। यह संरचना एक निश्चित आकार के साथ एक सरणी हो सकती है (प्रस्थान के अधिकतम दिन द्वारा निर्धारित)।

इनपुट डेटा:
- प्रविष्टियाँ = [1, 3, 5]
- प्रस्थान = [२, ६, १०]
- के = १

इस उदाहरण के लिए, सरणी का आकार 10 होगा (क्योंकि 10 वें दिन अंतिम निकास)। इस सरणी को भरने के लिए, हम प्रविष्टियों की सूची से बाहर निकलते हैं और उसी दिन के काउंटर को बढ़ाते या घटाते हैं। छद्म कोड उदाहरण:

int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- } 

परिणामस्वरूप, हमें निम्न सरणी मिलती है:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

सरणी भर जाने के बाद, आपको बस इसके माध्यम से जाने की जरूरत है और जांच लें कि क्या सभी तत्व k (कमरों की संख्या) से अधिक नहीं हैं।

पिछले उदाहरण में, कमरों की अधिकतम संख्या 1. थी 5 दिन के बाद से हमारे पास 2 आरक्षण हैं, हम false ।

इस समाधान की समय जटिलता O (n) है, जहाँ n आरक्षण की संख्या है, और स्थानिक O (m) है, जहाँ m अधिकतम प्रस्थान दिवस है। सिद्धांत में बुरा नहीं है, लेकिन यह एक बड़े सरणी के लिए बहुत सारी मेमोरी आवंटित करने की संभावना है, हालांकि इसका अधिकांश उपयोग नहीं किया जाएगा।

उदाहरण के लिए:

इनपुट डेटा:
- प्रविष्टियाँ = [1, 3, 5]
- प्रस्थान = [२, १००००, १०]
- के = १

इस स्थिति में, 10 हजार पूर्णांकों की एक सरणी आवंटित की जाएगी।

आइए अन्य समाधानों को देखें।

घटना संग्रह संग्रहण

अन्य विकल्प क्या हैं? आइए फिर से देखें कि पिछली संरचना के साथ क्या हुआ था:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

हम देखते हैं कि कुछ जानकारी डुप्लिकेट है। उदाहरण के लिए, 6 और 9 दिनों के बीच बुकिंग की संख्या नहीं बदलती है, क्योंकि हम जानते हैं कि इस अवधि के दौरान कुछ भी नहीं होगा।

क्या इसके बजाय घटनाओं को संग्रहीत किया जाए तो बेहतर हो सकता है? चलिए फिर से एक ही उदाहरण लेते हैं:

इनपुट डेटा:
- प्रविष्टियाँ = [1, 3, 5]
- प्रस्थान = [२, ६, १०]
दिन 1: +1 बुकिंग
दिन 2: -1 बुकिंग
दिन 3: +1 बुकिंग
दिन 6: -1 बुकिंग
दिन 5: +1 बुकिंग
दिन 10: -1 बुकिंग

समाधान काउंटर बढ़ाने या घटाने के लिए इन घटनाओं पर पुनरावृति करना है। यदि किसी बिंदु पर काउंटर k से अधिक है, तो हम false लौटते हैं। हालाँकि, इसे पुन: व्यवस्थित करने के लिए, इस संग्रह को क्रमबद्ध करना होगा।

यहां उपयोग करने के लिए कौन सी संरचना बेहतर है? चलो हमारी आवश्यकताओं को संक्षेप में प्रस्तुत करते हैं:

• यह जांचने के लिए खोजें कि क्या ऐसा दिन पहले से मौजूद है
• एक नया दिन जोड़ना,
• प्रत्येक छांटे गए दिन में पुनरावृति करने के लिए संरचना देखें।

बाइनरी सर्च ट्री (BST) का उपयोग कैसे करें?

प्रत्येक नोड को निम्नानुसार दर्शाया जा सकता है:

 class Node { int day int count Node left Node right } 

day क्षेत्र में छंटाई की जाएगी।

आइए समय जटिलता के संदर्भ में परिणामों को देखें:

• यह जांचने के लिए खोजें कि क्या ऐसा दिन पहले से मौजूद है: ओ (लॉग (एन)) औसत मामले में, सबसे खराब स्थिति में ओ (एन),
• एक नया दिन जोड़ना: ओ (लॉग (एन)) औसत मामले में, सबसे खराब स्थिति में ओ (एन),
• प्रत्येक सॉर्ट किए गए दिन से अधिक पुनरावृति के लिए संरचना देखें: O (n) एक गहन खोज का उपयोग करते हुए।

चूंकि हमें प्रत्येक तत्व के माध्यम से सॉर्ट करना है और इसे पेड़ में डालना है, एल्गोरिथ्म की जटिलता औसत मामले में ओ (एन लॉग (एन)) है, सबसे खराब स्थिति में ओ (एन)।

एक अन्य विकल्प हैश तालिका का उपयोग करना और सभी घटनाओं को जोड़ने के बाद कुंजियों को क्रमबद्ध करना है:

• यह जांचने के लिए खोजें कि क्या ऐसा दिन पहले से मौजूद है: ओ (1) औसत मामले में, ओ (एन) सबसे खराब स्थिति में (संभावना साहचर्य सरणी की क्षमता पर निर्भर करती है),
• एक नया दिन जोड़ना: ओ (1) औसत मामले में, सबसे खराब स्थिति में ओ (एन),
• प्रत्येक छांटे गए दिन से अधिक के लिए संरचना देखें: छँटाई के लिए O (n लॉग (n)) और छँटाई के लिए O (n)।

अंत में, मध्यम मामले में समाधान में ओ (एन लॉग (एन)) है (सॉर्ट ऑपरेशन के कारण), सबसे खराब स्थिति में ओ (एन)। इस समाधान में वृक्ष-आधारित समाधान के समान जटिलता है।

आइए एक क्रमबद्ध साहचर्य सरणी का उपयोग करके जावा में संभावित कार्यान्वयन को देखें:

 public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { //   Map<Integer, Integer> events = new HashMap<>(); //   int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); //      Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); //      current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } //    Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); //  count     if (count > k) { return false; } } return true; } 

लगातार स्थानिक जटिलता

यदि हम अपने एल्गोरिथ्म को अनुकूलित करना चाहते हैं, तो हमें यह सोचने की ज़रूरत है कि क्या इन सभी घटनाओं को संग्रहीत करना वास्तव में आवश्यक है? क्या हम केवल संग्रह डेटा (प्रविष्टियों और निकास) के माध्यम से क्रमबद्ध नहीं कर सकते हैं और प्रक्रिया में आरक्षण की सीमा की जांच कर सकते हैं?

एक समाधान संभव है, लेकिन इसके लिए पहले से छंटाई करके इनपुट डेटा को सरल बनाना आवश्यक होगा।

यदि दोनों संग्रहों को क्रमबद्ध किया जाता है, तो हम बस दो बिंदुओं (प्रवेश के लिए एक और निकास के लिए एक) का उपयोग करके प्रत्येक तत्व पर पुनरावृति कर सकते हैं, और मक्खी पर प्रतिबंध की जांच कर सकते हैं।

जैसा कि आप देख सकते हैं, प्रत्येक पुनरावृत्ति के दौरान हमें अभी भी arrivals.get(indexArrival) departures.get(indexDeparture) बीच न्यूनतम जाँच करने की आवश्यकता है। arrivals.get(indexArrival) departures.get(indexDeparture) यह पता लगाने के लिए कि सूचक को अद्यतन करने की आवश्यकता है।

सामान्य तौर पर, एल्गोरिथ्म में निरंतर अस्थायी और स्थानिक जटिलता ओ (एन लॉग (एन)) छँटाई संचालन के कारण होती है।