Fenwick tree और कम्प्रेशन से ओवरलैपिंग अंतराल की अधिकतम टीम

शेड्यूल ओवरलैप से अधिकतम टीम आकार निकालें: Fenwick tree व कोऑर्डिनेट कम्प्रेशन आधारित O(N log N) एल्गोरिदम, सहज व्याख्या, Python उदाहरण और कोड सहित.

जब शेड्यूल आपस में ओवरलैप करते हैं, तो टीम बन सकती है। काम स्पष्ट है: N कर्मचारियों के लिए शुरुआत और समाप्ति समय दिए गए हैं, और अंतराल दोनों सिरों पर समावेशी हैं; ऐसी टीम का अधिकतम आकार निकालना है जिसमें हर सदस्य समूह के एक विशिष्ट व्यक्ति के साथ ओवरलैप करता हो। उदाहरण के लिए startTime = [2,5,6,8] और endTime = [5,6,10,9] पर उत्तर 3 है।

समस्या का सार

हमें समान लंबाई के दो ऐरे दिए गए हैं: शुरुआत के समय और समाप्ति के समय। कोई कर्मचारी दूसरे के साथ तभी टीम बना सकता है जब उनके काम के घंटे एक-दूसरे से कटते हों, और ठीक सीमा पर छूना भी मान्य है। किसी कर्मचारी के लिए टीम का आकार = उसके साथ ओवरलैप करने वाले कर्मचारियों की संख्या + स्वयं। लक्ष्य है सभी कर्मचारियों में से अधिकतम टीम आकार खोजना। चर्चा की भाषा में, समूह के भीतर जोड़े-जोड़े का इंटरसेक्शन जरूरी नहीं; शर्त यह है कि समूह के सभी अंतराल उस समूह के एक विशेष अंतराल से कटते हों।

सरल लेकिन समय-सीमा पार कर देने वाला तरीका

सीधा तरीका हर जोड़ी को परखकर ओवरलैप गिनता है। लिखना आसान है और समझ में आता है, लेकिन जटिलता O(N²) है। कर्मचारियों की संख्या बढ़ते ही यह समय से बाहर हो जाएगा।

begins = [2,5,6,8]
finishes = [5,6,10,9]
m = len(begins)
best = 0
for a in range(m):
    cur = 0
    for b in range(m):
        if a == b:
            continue
        if ((begins[a] <= begins[b] <= finishes[a]) or (begins[a] <= finishes[b] <= finishes[a])):
            cur += 1
    best = max(best, cur)
print(best + 1)

यह उदाहरण के लिए सही मान छापता है, लेकिन अंदरूनी लूप O(N²) में चलता है, जो बड़े इनपुट पर टिकाऊ नहीं है।

यह धीमा क्यों है

ब्रूट-फोर्स लूप हर अंतराल की तुलना हर दूसरे से करता है। ओवरलैप जांच O(1) है, फिर भी तुलना की भारी संख्या समय खा जाती है। स्केल करने के लिए तुलना घटानी होगी और ओवरलैप की गिनती को कुशलता से समेकित करना होगा।

O(N log N) में अनुकूलित तरीका

अंतरालों को शुरुआत समय के आधार पर सॉर्ट करने से एक रैखिक पास के साथ उप-रैखिक अपडेट संभव होते हैं। विचार यह है: हर अंतराल के लिए देखें कि उससे पहले कितने अंतराल उससे ओवरलैप करते हैं (बाएँ), और उसके बाद कितने उससे ओवरलैप करते हैं (दाएँ)। इनका योग उस विशेष अंतराल के लिए टीम के साथियों की संख्या देता है; अधिकतम योग ही उत्तर है। दोनों पास एक बाइनरी इंडेक्स्ड ट्री (Fenwick tree) पर निर्भर करते हैं, जो सभी एंडपॉइंट्स के कोऑर्डिनेट कम्प्रेशन पर बनाया गया है। कम्प्रेशन मनमाने समयों को इंडेक्स में मैप करके Fenwick ट्री को छोटा रखता है। फॉरवर्ड पास में हम पिछले समाप्ति समयों का मल्टीसेट रखते हैं। वर्तमान शुरुआत के लिए, जितने भी पिछले समाप्ति समय इस शुरुआत से बड़े या बराबर हैं, वे बाएँ तरफ ओवरलैप दर्शाते हैं। बैकवर्ड पास में हम आने वाले शुरुआत समयों का मल्टीसेट रखते हैं। वर्तमान समाप्ति के लिए, जितने भी आने वाले शुरुआत समय इस समाप्ति से छोटे या बराबर हैं, वे दाएँ तरफ ओवरलैप दर्शाते हैं। जब कई अंतरालों की शुरुआत समान हो, तो उन्हें समूहित करना सुसंगतता बनाए रखता है।

from bisect import bisect_left as bleft
import itertools as it
def max_team(begins: list[int], finishes: list[int]):
    coords = sorted(begins + finishes)
    tree = [0] * len(coords)
    def add(pos, val):
        while pos < len(tree):
            tree[pos] += val
            pos |= pos + 1
    def pref(pos):
        acc = 0
        while pos >= 0:
            acc += tree[pos]
            pos = (pos & (pos + 1)) - 1
        return acc
    order = sorted(range(len(finishes)), key=lambda k: begins[k])
    left_cnt = [0] * len(finishes)
    for _, grp in it.groupby(order, key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            left_cnt[idx] = pref(len(tree) - 1) - pref(bleft(coords, begins[idx]) - 1)
        for idx in seq:
            add(bleft(coords, finishes[idx]), 1)
    tree = [0] * len(tree)
    peak = 0
    for _, grp in it.groupby(reversed(order), key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            add(bleft(coords, begins[idx]), 1)
        for idx in seq:
            total = left_cnt[idx] + pref(bleft(coords, finishes[idx]))
            if total > peak:
                peak = total
    return peak
# उदाहरण सत्यापन
print(max_team([2,5,6,8], [5,6,10,9]))  # अपेक्षित: 3

यह कार्यान्वयन O(N log N) में चलता है। यह हर अंतराल के लिए बाईं और दाईं ओर से ओवरलैप की संख्या (समावेशी सीमाओं के साथ) गिनता है और आवश्यकतानुसार अधिकतम टीम आकार लौटाता है। दिए गए उदाहरण पर परिणाम 3 आता है।

यह क्यों मायने रखता है

ओवरलैपिंग अंतरालों पर आधारित समस्याएँ शेड्यूलिंग, संसाधन आवंटन, लॉग विश्लेषण और रियल-टाइम मॉनिटरिंग में आम हैं। O(N²) और O(N log N) का अंतर प्रोटोटाइप और प्रोडक्शन के बीच की दूरी तय करता है। कोऑर्डिनेट कम्प्रेशन के साथ Fenwick tree तेज प्रीफिक्स सम के लिए एक व्यावहारिक पैटर्न है, खासकर जब मान बड़े या मनमाने डोमेन से आते हों।

मुख्य बातें

ओवरलैप की परिभाषा साफ रखें; यहाँ सीमाएँ समावेशी हैं और वैध टीम एक विशेष अंतराल से इंटरसेक्शन पर निर्भर करती है। द्विघात स्कैन की जगह सॉर्टेड स्वीप और इंडेक्स्ड एग्रीगेट अपनाएँ। संकुचित निर्देशांकों पर बना बाइनरी इंडेक्स्ड ट्री यह गिनने का कॉम्पैक्ट और तेज़ तरीका देता है कि वर्तमान अंतराल में किन-किन पूर्ववर्ती या आगामी अंतरालों का योगदान है। इससे अधिकतम टीम आकार कुशलता और निश्चितता के साथ निकाला जा सकता है।