Intervals

पहले हमेशा sort करें

लगभग हर interval समस्या intervals को start time से sort करने से शुरू होती है (scheduling के लिए end time से)। Sort होने के बाद, overlaps और gaps all-pairs खोज के बजाय पड़ोसी तुलना बन जाते हैं।

Overlapping intervals मिलाएँ

Start से sort करने के बाद, आगे बढ़ें और जब भी मौजूदा interval का start, आखिरी merged interval के end से <= हो, मिलाएँ।

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    return merged

Output:

merge([[1,3],[2,6],[8,10],[15,18]])
# [[1,6],[8,10],[15,18]]

Interval scheduling (अधिकतम non-overlapping)

सबसे अधिक non-overlapping intervals फिट करने के लिए, end time से sort करें और जब भी कोई interval पिछले रखे गए interval के end के बाद शुरू हो, उसे greedily रखें।

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Output:

max_non_overlapping([[1,2],[2,3],[3,4],[1,3]])  # 3

आम variants

एक sorted list में नया interval डालना, न्यूनतम meeting rooms चाहिए (end times का heap इस्तेमाल करें), और क्या कोई व्यक्ति सभी meetings में जा सकता है — सब उसी sort-फिर-scan विचार पर बने हैं।