Patterns

Sort intervals by start; iterate and merge overlapping

When to useMerge intervals, insert interval, meeting rooms

iterative

Intervals

interval_pattern_intro

Can Attend Meetingseasy

can_attend_meetings · no slots

Minimum Number Of Arrows To Burst Balloonsmedium

minimum_number_of_arrows_to_burst_balloons · no slots

Non Overlapping Intervalsmedium

non_overlapping_intervals · no slots

INITIALIZE

sort intervals by start time; result = [intervals[0]]

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

intervals.push(newInterval);
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];

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

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

—

TRAVERSE

for each remaining interval

for (let i = 1; i < sorted.length; i++) {

for (let i = 1; i < intervals.length; i++) {

for (let i = 1; i < intervals.length; i++) {

for (let i = 1; i < sorted.length; i++) {

—

[MERGE]

if overlaps with last in result, extend end; else push as new

  const last = result[result.length - 1];
  if (sorted[i][0] <= last[1]) {
    last[1] = Math.max(last[1], sorted[i][1]);
  } else {
    result.push(sorted[i]);
  }

  const last = result[result.length - 1];
  if (intervals[i][0] <= last[1]) {
    last[1] = Math.max(last[1], intervals[i][1]);
  } else {
    result.push(intervals[i]);
  }

  if (intervals[i][0] < intervals[i - 1][1]) return false;

  const last = result[result.length - 1];
  if (sorted[i][0] <= last[1]) {
    last[1] = Math.max(last[1], sorted[i][1]);
  } else {
    result.push(sorted[i]);
  }

—

RETURN

return result

return result;

return result;

return true;

return result;

—