মূল কনটেন্টে যান
🌍
গ্লোবাল DSA
প্যাটার্ন•টপিক 1 · Arrays & Strings

1.5 Merge Intervals

চিনবেন কীভাবে
(start, end) pairs, "overlap", "merge", "meeting rooms", scheduling — almost always sort by start first
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Merge Intervals — LC 56 (Medium — frequent everywhere)

Statement (Demo): Given intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals and return the non-overlapping result. Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] | ⚡ n ≤ 10⁴, 0 ≤ startᵢ ≤ endᵢ ≤ 10⁴

Approach: Sort by start. In one pass, if the next interval starts inside the last merged interval, extend its end; otherwise push it as a new interval.

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const [s, e] = intervals[i];
    const last = res[res.length - 1];
    if (s <= last[1])
      last[1] = Math.max(last[1], e); // overlap → merge
    else res.push([s, e]);
  }
  return res;
}

Complexity: Time O(n log n) (sort), Space O(n)

Demo · Merge Intervalsplan · দিন ০০৮LC 56
নোট · ফাঁকা

প্রবলেম

  • Insert Intervalplan · দিন ০২৩🔥 Must-doLC 57

    Statement: Given sorted non-overlapping intervals and a new interval, insert it (merging where needed) and return a sorted non-overlapping list.
    Example: intervals=[[1,3],[6,9]], newInterval=[2,5] → [[1,5],[6,9]] | ⚡ n ≤ 10⁴

    নোট · ফাঁকা
  • Non-overlapping Intervalsplan · দিন ০৪৪🔥 Must-doLC 435
    (greedy: sort by end — see 10.1 too)

    Statement: Given an array of intervals, return the minimum number to remove so the rest do not overlap.
    Example: [[1,2],[2,3],[3,4],[1,3]] → 1 (remove [1,3]) | ⚡ n ≤ 10⁵

    নোট · ফাঁকা
  • Meeting RoomsLC 252
    (Premium; free alternative: GfG "meeting rooms")

    Statement: Given meeting intervals [start, end], decide whether one person can attend all of them (no two overlap).
    Example: [[0,30],[5,10],[15,20]] → false | ⚡ n ≤ 10⁴

    নোট · ফাঁকা