🟡 Merge Intervals

<aside> 💡 Sort, insert first, iterate (merge or just push).

</aside>

https://leetcode.com/problems/merge-intervals/

function merge(intervals) {
  const result = [];

  // sort
  intervals.sort((a, b) => a[0] - b[0]);

  // insert first
  result.push(intervals[0]);

  // iterate
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] <= result[result.length - 1][1]) {
      // merge
      result[result.length - 1] = [result[result.length - 1][0],  Math.max(result[result.length - 1][1], intervals[i][1])];
    } else {
      // push
      result.push(intervals[i]);
    }
  }

  return result;
}

• Idea

🟡 Non-overlapping Intervals

<aside> 💡 Sort. No overlap - update previous. Overlap - pick the one that has longer end.

</aside>

https://leetcode.com/problems/non-overlapping-intervals/

function eraseOverlapIntervals(intervals) {
  let count = 0;

  intervals.sort((a, b) => a[0] - b[0]);

  let prevEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= prevEnd) {
      prevEnd = intervals[i][1];
    } else {
      count++;
      prevEnd = Math.min(prevEnd, intervals[i][1]);
    }
  }

  return count;
}

• Idea

🟢 Meeting Rooms