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

1.5 Merge Intervals

চিনবেন কীভাবে
(start, end) pair, "overlap", "merge", "meeting rooms", scheduling — প্রায় সবসময় আগে start দিয়ে sort
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Merge Intervals — LC 56 (Medium — সব কোম্পানিতে ঘন ঘন)

Statement (Demo): intervals array দেওয়া যেখানে প্রতিটা intervals[i] = [startᵢ, endᵢ]। সব overlapping interval merge করে non-overlapping interval-এর array return করুন। উদাহরণ: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] | ⚡ n ≤ 10⁴, 0 ≤ startᵢ ≤ endᵢ ≤ 10⁴

Approach: start অনুযায়ী sort করুন। এরপর এক পাস — নতুন interval-এর start যদি result-এর শেষ interval-এর end-এর ভেতরে পড়ে, end বাড়িয়ে merge; নাহলে নতুন করে push।

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)

প্রবলেম

  • Insert Intervalplan · দিন ০৩৩LC 57

    Statement: non-overlapping sorted intervals আর একটা নতুন interval দেওয়া — নতুনটা insert করে (দরকার হলে merge করে) আবার non-overlapping sorted list return করুন।
    উদাহরণ: intervals=[[1,3],[6,9]], newInterval=[2,5] → [[1,5],[6,9]] | ⚡ n ≤ 10⁴

    নোট · ফাঁকা
  • Non-overlapping IntervalsLC 435
    (greedy: end অনুযায়ী sort — দেখুন 10.1-ও)

    Statement: intervals array দেওয়া — সব interval non-overlapping করতে minimum কয়টা interval সরাতে হবে বলুন।
    উদাহরণ: [[1,2],[2,3],[3,4],[1,3]] → 1 ([1,3] সরালেই হয়) | ⚡ n ≤ 10⁵

    নোট · ফাঁকা
  • Meeting RoomsLC 252
    (Premium; ফ্রি বিকল্প: GfG "meeting rooms")

    Statement: meeting time intervals [start, end] দেওয়া — একজন মানুষ সব meeting attend করতে পারবে কিনা বলুন (কোনো দুটো meeting overlap করলে পারবে না)।
    উদাহরণ: [[0,30],[5,10],[15,20]] → false | ⚡ n ≤ 10⁴

    নোট · ফাঁকা