कोडिंग इंटरव्यू: आवश्यक न्यूनतम मीटिंग रूम

प्रॉम्प्ट और उपयोग के मामले

आपको एक अनसॉर्टेड ऐरे intervals दिया गया है। प्रत्येक तत्व एक पूर्णांक समय अंतराल [start, end) है: start शामिल है और end अपवर्जित (excluded) है। इसलिए समय t पर समाप्त होने वाली मीटिंग अपने रूम को t पर शुरू होने वाली दूसरी मीटिंग के लिए खाली कर देती है। मान लें कि 0 <= intervals.length <= 100000 और 0 <= start < end <= 1000000000 है। प्रत्येक मीटिंग को शेड्यूल करने के लिए आवश्यक न्यूनतम कमरों (rooms) की संख्या लौटाएं।

उदाहरण के लिए, [[0, 30], [5, 10], [15, 20]] लौटाता है 2; [[1, 5], [5, 8]] लौटाता है 1; एक खाली ऐरे लौटाता है 0। ये इस लेख द्वारा अपनाई गई इंटरव्यू बाधाएं (constraints) हैं, किसी प्लेटफॉर्म के छिपे हुए प्रतिबंध नहीं।

सार्वजनिक सामग्री कई प्रकार के प्रतिनिधि साक्ष्य प्रदान करती है। PracHub ने 2026 में इसी प्रॉम्प्ट को अपडेट किया। interviewing.io न्यूनतम मीटिंग रूम को एक टाइमलाइन या प्रायोरिटी कतार के साथ हल करने योग्य अंतराल समस्या के रूप में प्रस्तुत करता है। फरवरी 2026 का एक सार्वजनिक इंटरव्यू विवरण टू पॉइंटर्स, एक प्रायोरिटी कतार, और एक सीमित समय डोमेन के लिए ऐरे पर फॉलो-अप दर्ज करता है। UMass एल्गोरिदम नोट्स मुख्य अंतराल-विभाजन (interval-partitioning) प्रमाण प्रदान करते हैं: जब अंतरालों को शुरू होने के समय के अनुसार प्रोसेस किया जाता है, तो ग्रीडी एल्गोरिदम द्वारा उपयोग किए जाने वाले कमरों की संख्या अधिकतम ओवरलैप गहराई के बराबर होती है। एक अकेला विवरण केवल उस उम्मीदवार के अनुभव को साबित करता है, इसलिए यह लेख न तो सामान्य साक्षात्कार आवृत्ति का अनुमान लगाता है और न ही इस प्रश्न को किसी एक कंपनी के निश्चित प्रश्न बैंक से जोड़ता है।

इंटरव्यूअर के मूल्यांकन मानदंड

पहला संकेत मॉडलिंग है। यह संसाधन-गणना की समस्या है, न कि अंतरालों को मर्ज करने या सबसे बड़े संगत सबसेट का चयन करने की। न्यूनतम रूम काउंट किसी भी क्षण चल रही मीटिंग्स की चरम (peak) संख्या के बराबर होता है, जिसे अक्सर इंटरवल सेट की गहराई (depth) कहा जाता है।

दूसरा संकेत एंडपॉइंट सिमेंटिक्स है। अर्ध-खुले (half-open) अंतरालों के साथ, एक ही समय पर होने वाले स्टार्ट इवेंट से पहले एंड इवेंट को प्रोसेस किया जाना चाहिए। start === end को ओवरलैप के रूप में मानने से [1, 5) और [5, 8) को गलत तरीके से दो कमरे आवंटित हो जाते हैं।

तीसरा संकेत इनवेरिएंट्स और प्रमाण है। एक बार जब स्टार्ट्स और एंड्स को अलग-अलग सॉर्ट कर दिया जाता है, तो पॉइंटर्स अब यह याद नहीं रखते कि कौन सा एंड किस मीटिंग का है। उम्मीदवार को यह समझाना चाहिए कि जब केवल समवर्ती अधिभोग (concurrent occupancy) मायने रखता है तो पहचान अप्रासंगिक क्यों है: यह जानना पर्याप्त है कि अगला इवेंट सबसे पहले उपलब्ध स्टार्ट है या एंड।

अंत में, इंटरव्यूअर बदलती आवश्यकताओं के तहत डेटा-स्ट्रक्चर चॉइस का परीक्षण कर सकता है। टू-ऐरे स्वीप सीधे काउंट लौटाता है। ठोस रूम असाइनमेंट, प्रत्येक मीटिंग द्वारा उपयोग किए गए कमरे, या पुन: उपयोग के इतिहास के अनुरोध के लिए एक min-heap की आवश्यकता होती है जो एंड टाइम और रूम आइडेंटिफायर्स दोनों को बनाए रखता है।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• क्या अंतराल [start, end) हैं या बंद (closed)? यह समस्या अर्ध-खुले अंतरालों का उपयोग करती है, इसलिए समान एंडपॉइंट्स पर टकराव नहीं होता है।
• क्या शून्य-लंबाई वाली मीटिंग्स मान्य हैं? यह अनुबंध start < end की आवश्यकता रखता है और [t, t) को अस्वीकार करता है। यदि कोई व्यवसाय इसकी अनुमति देता है, तो परिभाषित करें कि क्या वे संसाधन की खपत करते हैं।
• खाली इनपुट पर क्या लौटना चाहिए? पहली मीटिंग के किसी भी इनिशियलाइज़ेशन एरर से बचते हुए 0 लौटाएं।
• क्या हम केवल एक काउंट लौटाते हैं या असाइनमेंट भी? काउंट के लिए दो ऐरे पर्याप्त हैं; असाइनमेंट के लिए मीटिंग पहचान और पुन: प्रयोज्य कमरों को बनाए रखना आवश्यक है।
• क्या कार्यान्वयन इनपुट को म्यूटेट (परिवर्तित) कर सकता है? नीचे दिया गया कार्यान्वयन स्टार्ट और एंड मानों को कॉपी करता है और कॉलर के ऐरे को अछूता छोड़ देता है।
• क्या समय सुरक्षित पूर्णांक (safe integers) हैं? बताई गई ऊपरी सीमा जावास्क्रिप्ट के सेफ-इंटीजर रेंज के भीतर है। बड़े टाइमस्टैम्प्स के लिए एक नए रिप्रेजेंटेशन अनुबंध की आवश्यकता होती है।
• क्या इनपुट अमान्य हो सकता है? इंटरव्यू इनपुट आमतौर पर अनुबंध को संतुष्ट करते हैं। प्रोडक्शन वैलिडेशन मुख्य एल्गोरिदम के अंदर के बजाय सिस्टम बाउंड्री पर होना चाहिए।

30-सेकंड उत्तर ढांचा

“मैं पहले पुष्टि करूंगा कि अंतराल अर्ध-खुले हैं, ताकि दिए गए समय पर खाली हुआ कमरा तुरंत पुन: उपयोग किया जा सके। जब केवल न्यूनतम काउंट की आवश्यकता होती है, तो मैं स्टार्ट्स और एंड्स को अलग-अलग सॉर्ट करता हूं और उन्हें दो पॉइंटर्स के साथ स्कैन करता हूं। यदि अगला स्टार्ट सबसे पहले वाले एंड से पहले का है, तो मैं ऑक्यूपेंसी बढ़ाता हूं; अन्यथा, मैं पहले एक कमरा खाली करता हूं। मैं अधिकतम ऑक्यूपेंसी को बनाए रखता हूं।

वह चरम मान (peak) निचली सीमा (lower bound) भी है और प्राप्त करने योग्य भी: एक साथ होने वाली मीटिंग्स के लिए अलग-अलग कमरों की आवश्यकता होती है, और स्टार्ट समय के अनुसार प्रोसेस करने पर नया कमरा केवल तभी खोला जाता है जब मौजूदा सभी कमरे अभी भी भरे हों। सॉर्टिंग के कारण कुल समय O(n log n) और अतिरिक्त स्पेस O(n) होता है। यदि फॉलो-अप में ठोस असाइनमेंट पूछा जाता है, तो मैं एंड टाइम्स और रूम आइडेंटिफायर्स वाले min-heap का उपयोग करूंगा।”

चरण-दर-चरण समाधान

चरण 1: दो सॉर्ट किए गए इवेंट स्ट्रीम से पीक ऑक्यूपेंसी की गणना करें

प्रत्येक स्टार्ट टाइम को आरोही क्रम में starts में और प्रत्येक एंड टाइम को आरोही क्रम में ends में रखें। startIndex अगले अनप्रोसेस्ड स्टार्ट इवेंट को इंगित करता है, जबकि endIndex अगले अनप्रोसेस्ड एंड इवेंट को इंगित करता है। roomsInUse वर्तमान स्वीप स्थिति के तुरंत बाद अभी भी भरे हुए कमरों की संख्या है। मान्य अंतराल start < end को संतुष्ट करते हैं, इसलिए स्वीप कभी भी ऐसे समय एंड को प्रोसेस नहीं करता जब कोई मीटिंग सक्रिय न हो।

यदि starts[startIndex] < ends[endIndex] है, तो अगला इवेंट एक स्टार्ट है: ऑक्यूपेंसी बढ़ाएं और पीक को अपडेट करें। अन्यथा, पहले एक एंड को प्रोसेस करें और एक कमरा खाली करें। स्ट्रिक्ट 'लेस-दैन' (<) तुलना जानबूझकर की गई है। समान एंडपॉइंट्स अगले स्टार्ट से पहले रिलीज़ ब्रांच लेते हैं, जो पूरी तरह से [start, end) को लागू करता है।

export function minimumMeetingRooms(
  intervals: ReadonlyArray<readonly [number, number]>,
): number {
  if (intervals.length === 0) return 0

  const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
  const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)

  let startIndex = 0
  let endIndex = 0
  let roomsInUse = 0
  let maximumRooms = 0

  while (startIndex < intervals.length) {
    if (starts[startIndex] < ends[endIndex]) {
      roomsInUse += 1
      maximumRooms = Math.max(maximumRooms, roomsInUse)
      startIndex += 1
    } else {
      roomsInUse -= 1
      endIndex += 1
    }
  }

  return maximumRooms
}

[[0, 30], [5, 10], [15, 20]] को ट्रेस करें। स्टार्ट्स 0, 5, 15 हैं; एंड्स 10, 20, 30 हैं। 0 और 5 पर स्टार्ट ऑक्यूपेंसी को 0 से बढ़ाकर 2 कर देते हैं। 10 पर एंड एक कमरा खाली करता है, जिससे यह घटकर 1 हो जाता है। 15 पर स्टार्ट इसे फिर से बढ़ाकर 2 कर देता है। अधिकतम पीक 2 है।

चरण 2: सिद्ध करें कि पीक ही इष्टतम (optimum) है

पहला, स्वीप काउंट सही है। प्रत्येक [start, end) को एक +1 स्टार्ट इवेंट और एक -1 एंड इवेंट के रूप में दर्शाएं, समय के अनुसार सॉर्ट करें, और टाई होने पर स्टार्ट से पहले एंड को प्रोसेस करें। किसी भी इवेंट के बाद, रनिंग सम उन अंतरालों की संख्या के बराबर होता है जो तुरंत बाद टाइमलाइन को कवर करते हैं, जो ठीक भरे हुए कमरों की संख्या है। पॉइंटर्स के साथ दो सॉर्ट किए गए ऐरे को मर्ज करना सभी इवेंट्स को उसी क्रम में पार करता है।

अगला, सिद्ध करें कि पीक इष्टतम है। मान लें कि अधिकतम ओवरलैप गहराई d है। किसी क्षण, d मीटिंग्स एक साथ चलती हैं, इसलिए प्रत्येक शेड्यूल को कम से कम d कमरों की आवश्यकता होती है; यह एक निचली सीमा (lower bound) है। जब मीटिंग्स को स्टार्ट समय के अनुसार प्रोसेस किया जाता है, तो ग्रीडी असाइनमेंट एक नया कमरा केवल तभी खोलता है जब सभी मौजूदा कमरे उन मीटिंग्स द्वारा भरे हों जो समाप्त नहीं हुई हैं। यदि यह कमरा k खोलता है, तो नई मीटिंग और अन्य k - 1 मीटिंग्स उस क्षण सह-अस्तित्व में हैं, इसलिए k <= d। इसलिए केवल d कमरों का उपयोग करने वाला एक शेड्यूल मौजूद है। साध्य ऊपरी सीमा निचली सीमा के बराबर है, इसलिए न्यूनतम d है, जो बिल्कुल स्वीप द्वारा लौटाया गया पीक है।

ऐरे बनाने में O(n) लागत आती है, दो सॉर्ट में O(n log n) लागत आती है, और मर्ज स्कैन में O(n) लागत आती है। कुल समय O(n log n) और अतिरिक्त स्पेस O(n) है। यदि समय एक छोटे, निश्चित असतत (discrete) डोमेन से आता है, तो एक डिफरेंस ऐरे इसे O(n + U) समय और O(U) स्पेस में बदल सकता है। जब समय सीमा एक अरब हो, तो वह अनुकूलन उपयुक्त नहीं है।

चरण 3: आवश्यकताएं बदलने पर हीप या डिफरेंस ऐरे चुनें

एक अन्य समाधान मीटिंग्स को स्टार्ट टाइम के अनुसार सॉर्ट करता है और प्रत्येक भरे हुए कमरे के एंड टाइम को एक min-heap में रखता है। किसी मीटिंग को प्रोसेस करने से पहले, end <= start वाली प्रत्येक प्रविष्टि को पॉप करें, फिर नया एंड टाइम पुश करें। हीप का पीक साइज ही उत्तर है। इसमें भी O(n log n) समय और सबसे खराब स्थिति में O(n) स्पेस लगता है।

केवल एक काउंट के लिए, स्वीप छोटा है और उस नियम को स्पष्ट करता है कि टाई होने पर एंड स्टार्ट से पहले आता है। हीप एक्सटेंशन के लिए मूल्यवान है: प्रत्येक प्रविष्टि को end से बदलकर { end, roomId } करें। उपलब्ध रूम आइडेंटिफायर्स का एक दूसरा min-heap बनाए रखें, मीटिंग्स समाप्त होने के बाद आइडेंटिफायर्स को पुनः प्राप्त करें, और प्रत्येक मूल मीटिंग इंडेक्स को एक ठोस कमरे में मैप करें। यदि आवश्यकता सबसे कम संख्या वाले उपलब्ध कमरे को चुनने की है, तो केवल सबसे शुरुआती एंड टाइम से चुनना अपर्याप्त है; भरे हुए और उपलब्ध कमरों को अलग-अलग प्रबंधित किया जाना चाहिए।

डायनामिक ऑनलाइन बुकिंग एक अलग समस्या है। जब भविष्य की मीटिंग्स व्यक्तिगत रूप से आती हैं और रद्द हो सकती हैं, तो प्रत्येक अंतराल को बार-बार सॉर्ट करना बहुत महंगा हो सकता है। क्वेरी वर्कलोड के लिए एक ऑर्डर्ड इवेंट स्टोर, इंटरवल ट्री, या कैलेंडर इंडेक्स की आवश्यकता हो सकती है। O(n log n) ऑफलाइन-ऐरे उत्तर को पूर्ण ऑनलाइन सिस्टम डिज़ाइन के रूप में प्रस्तुत नहीं किया जाना चाहिए।

उच्च गुणवत्ता वाला नमूना उत्तर

“मैं इसे [start, end) के तहत हल करूंगा, जिससे एक एंड दूसरे स्टार्ट के बराबर होने पर कमरे का पुनः उपयोग किया जा सके। पेयरवाइज़ कन्फ्लिक्ट चेकिंग एक मान्य बेसलाइन है लेकिन सबसे खराब स्थिति में इसकी लागत O(n^2) होती है। 100,000 मीटिंग्स तक के लिए, मैं इवेंट्स को सॉर्ट करूंगा।

मैं सॉर्ट किए गए स्टार्ट और एंड ऐरे बनाता हूं। दो पॉइंटर्स अगले इवेंट का निर्धारण करते हैं: एक शुरुआती स्टार्ट वर्तमान ऑक्यूपेंसी को बढ़ाता है और अधिकतम को अपडेट करता है; एक शुरुआती या टाई वाला एंड पहले ऑक्यूपेंसी को घटाता है। [[0, 30], [5, 10], [15, 20]] के लिए, ऑक्यूपेंसी 1, 2, 1, और 2 के माध्यम से बदलती है, इसलिए उत्तर 2 है।

शुद्धता के दो भाग हैं। रनिंग स्वीप काउंट सक्रिय अंतरालों की संख्या के बराबर होता है, इसलिए इसका अधिकतम मान ओवरलैप गहराई d है। जब वे मीटिंग्स सह-अस्तित्व में होती हैं तो प्रत्येक शेड्यूल को कम से कम d कमरों की आवश्यकता होती है। स्टार्ट-टाइम ग्रीडी असाइनमेंट केवल तभी एक कमरा जोड़ता है जब सभी मौजूदा कमरे भरे हों, इसलिए यह कभी भी d से अधिक का उपयोग नहीं करता है। यह एल्गोरिदम इष्टतम है। इसमें O(n log n) समय और O(n) स्पेस लगता है। यदि मुझे प्रत्येक मीटिंग के रूम आइडेंटिफायर की आवश्यकता है, तो मैं मूल इंडेक्स बनाए रखूंगा और एंड-टाइम हीप प्लस उपलब्ध-आइडेंटिफायर हीप के साथ कमरे आवंटित करूंगा।”

सामान्य गलतियां

• गलती: इंटरवल मर्जिंग को हल करना। यह क्यों विफल होता है: मर्ज किए गए अंतरालों की संख्या पीक समवर्ती ऑक्यूपेंसी का निर्धारण नहीं करती है। सुधार: स्टार्ट और एंड इवेंट्स को स्वीप करें और एक्टिव-काउंट पीक को बनाए रखें।
• गलती: समान एंडपॉइंट्स पर एंड से पहले स्टार्ट को प्रोसेस करना। यह क्यों विफल होता है: जिस कमरे का तुरंत पुन: उपयोग किया जा सकता है, उसे दो बार गिन लिया जाता है। सुधार: हाफ-ओपन अनुबंध के तहत एंड इवेंट्स को प्राथमिकता दें।
• गलती: जावास्क्रिप्ट के डिफ़ॉल्ट सॉर्ट का उपयोग करना। यह क्यों विफल होता है: लेक्सिकोग्राफिक क्रम 10 को 2 से पहले रखता है। सुधार: (a, b) => a - b स्पष्ट रूप से पास करें।
• गलती: अंतिम roomsInUse लौटाना। यह क्यों विफल होता है: अंतिम ऑक्यूपेंसी पहले के पीक से कम हो सकती है। सुधार: प्रत्येक स्टार्ट पर maximumRooms अपडेट करें।
• गलती: मीटिंग्स के हर जोड़े की तुलना करना। यह क्यों विफल होता है: सबसे खराब स्थिति का समय O(n^2) हो जाता है। सुधार: दो इवेंट स्ट्रीम्स को सॉर्ट करें और लीनियर रूप से मर्ज करें।
• गलती: असाइनमेंट तैयार करते समय केवल एक समाप्त मीटिंग को पॉप करना। यह क्यों विफल होता है: सक्रिय और उपलब्ध सेट अधूरे हो जाते हैं। सुधार: end <= start वाले प्रत्येक कमरे को पॉप करें और पुन: प्रयोज्य आइडेंटिफायर्स को अलग से प्रबंधित करें।
• गलती: इंटरवल सीमाओं को अपरिभाषित छोड़ना। यह क्यों विफल होता है: टेस्ट समान एंडपॉइंट्स पर असहमत होंगे। सुधार: कोडिंग से पहले हाफ-ओपन या क्लोज्ड इंटरवल्स और टाई-इवेंट प्राथमिकता को परिभाषित करें।
• गलती: सार्वजनिक प्रश्न-बैंक लेबल से कंपनी एट्रिब्यूशन जोड़ना। यह क्यों विफल होता है: थर्ड-पार्टी टैग और एक उम्मीदवार का विवरण निश्चित स्वामित्व साबित नहीं करते हैं। सुधार: सबूत अपर्याप्त होने पर companyName को null के रूप में रखें और केवल वही बताएं जिसका प्रत्येक स्रोत समर्थन करता है।

फॉलो-अप प्रश्न और उत्तर

दो सॉर्ट किए गए ऐरे मीटिंग के परस्पर संबंध (correspondence) को क्यों छोड़ सकते हैं?

उद्देश्य केवल प्रत्येक क्षण सक्रिय-मीटिंग गणना पर निर्भर करता है। अगला काउंट परिवर्तन सबसे शुरुआती अनप्रोसेस्ड स्टार्ट और सबसे शुरुआती अनप्रोसेस्ड एंड द्वारा निर्धारित होता है, भले ही वह एंड किसी भी मीटिंग का हो। असाइनमेंट या प्रति-मीटिंग ट्रेस के लिए संबंध फिर से आवश्यक हो जाता है, इसलिए उन आवश्यकताओं के लिए मीटिंग इंडेक्स और रूम आइडेंटिफायर्स वाले हीप का उपयोग करें।

बंद अंतरालों (closed intervals) [start, end] के लिए क्या बदलता है?

एक ही समय पर एक एंड और एक स्टार्ट में टकराव होता है। तुलना में स्टार्ट को पहले प्रोसेस किया जाना चाहिए, जिससे start <= end होने पर ऑक्यूपेंसी बढ़ जाती है। केवल एक ऑपरेटर को यंत्रवत बदलने के बजाय टाई प्राथमिकता को स्पष्ट रूप से परिभाषित करना अधिक सुरक्षित व्याख्या है।

आप प्रत्येक मीटिंग के लिए एक रूम आइडेंटिफायर कैसे लौटाएंगे?

मूल इंडेक्स बनाए रखें और स्टार्ट टाइम के अनुसार सॉर्ट करें। भरे हुए कमरों को { end, roomId } के min-heap में रखें। प्रत्येक मीटिंग से पहले, end <= start वाले प्रत्येक कमरे को उपलब्ध आइडेंटिफायर्स के min-heap में ले जाएं। सबसे छोटे उपलब्ध आइडेंटिफायर का पुन: उपयोग करें या एक नया बनाएं, फिर assignment[originalIndex] = roomId रिकॉर्ड करें।

न्यूनतम रूम काउंट अधिकतम ओवरलैप के बराबर क्यों होता है?

अधिकतम ओवरलैप एक अपरिहार्य निचली सीमा (lower bound) है क्योंकि एक साथ होने वाली मीटिंग्स कमरे साझा नहीं कर सकती हैं। स्टार्ट-टाइम ग्रीडी एल्गोरिदम एक कमरा केवल तभी खोलता है जब प्रत्येक मौजूदा कमरा अभी भी भरा हो। इसलिए इसके द्वारा खोला गया प्रत्येक कमरा उस क्षण ओवरलैप होने वाली मीटिंग्स की समान संख्या से मेल खाता है, इसलिए यह कभी भी निचली सीमा से अधिक नहीं होता है। समानता इष्टतमता को सिद्ध करती है।

किन एज केसेस का परीक्षण किया जाना चाहिए?

कम से कम, एक खाली ऐरे, एक अंतराल, कोई ओवरलैप नहीं, पूर्ण ओवरलैप, समान एंडपॉइंट्स की चेन, समान स्टार्ट्स, समान एंड्स, डुप्लिकेट अंतराल, रिवर्स-सॉर्टेड इनपुट, और आकार सीमा के करीब रैंडमाइज़्ड डेटा का परीक्षण करें। एक छोटा O(n^2) या असतत-इवेंट ओरेकल रैंडम डिफरेंशियल टेस्टिंग का समर्थन कर सकता है, लेकिन वन-ऑफ सत्यापन कोड को प्रोडक्शन कार्यान्वयन में मिश्रित नहीं किया जाना चाहिए।

क्या एक छोटा समय डोमेन एक लीनियर-टाइम समाधान दे सकता है?

हाँ। समय डोमेन U के समानुपाती आकार के डिफरेंस ऐरे का उपयोग करें, प्रत्येक स्टार्ट पर एक जोड़ें, प्रत्येक एंड पर एक घटाएं, और पीक प्रीफिक्स सम लें। इसकी जटिलता O(n + U) समय और O(U) स्पेस है। यह केवल तभी सार्थक है जब U छोटा हो और मेमोरी नियंत्रित हो; वर्तमान एक अरब की सीमा के तहत सॉर्टिंग अधिक सुरक्षित है।