Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// Two intervals overlap when each starts before the other ends.
function overlaps(a, b) {
  return a[0] < b[1] && b[0] < a[1];
}

// If the endpoints are inclusive (a meeting from 1 to 3 occupies minute 3),
// use <= instead. Ask the interviewer which convention applies.
function overlapsInclusive(a, b) {
  return a[0] <= b[1] && b[0] <= a[1];
}

console.log('[1,3] vs [2,4]:', overlaps([1, 3], [2, 4]));      // true, they cross
console.log('[1,3] vs [3,5]:', overlaps([1, 3], [3, 5]));      // false, they only touch
console.log('[1,3] vs [3,5] inclusive:', overlapsInclusive([1, 3], [3, 5]));  // true
console.log('[1,9] vs [3,4]:', overlaps([1, 9], [3, 4]));      // true, one contains the other
console.log('[1,2] vs [5,6]:', overlaps([1, 2], [5, 6]));      // false, disjoint

// The overlapping region itself, when there is one.
function intersection(a, b) {
  const lo = Math.max(a[0], b[0]), hi = Math.min(a[1], b[1]);
  return lo < hi ? [lo, hi] : null;
}
console.log('overlap of [1,5] and [3,8]:', intersection([1, 5], [3, 8]));   // [3,5]
console.log('overlap of [1,2] and [8,9]:', intersection([1, 2], [8, 9]));   // null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function merge(intervals) {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [sorted[0].slice()];       // copy, so we never mutate the input

  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const [start, end] = sorted[i];

    if (start <= last[1]) {
      // Overlaps or touches the interval we are building: extend it.
      last[1] = Math.max(last[1], end);     // max matters: [1,10] then [2,3]
    } else {
      merged.push([start, end]);            // a gap, so begin a new one
    }
  }
  return merged;
}

console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));   // [[1,6],[8,10],[15,18]]
console.log(merge([[1, 4], [4, 5]]));                      // [[1,5]] touching merges
console.log(merge([[1, 10], [2, 3], [4, 5]]));             // [[1,10]] fully contained
console.log(merge([[5, 6], [1, 2]]));                      // [[1,2],[5,6]] unsorted input
console.log(merge([[1, 4]]));                              // [[1,4]]
console.log(merge([]));                                    // []

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function mergeBroken(intervals) {
  const s = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [s[0].slice()];
  for (let i = 1; i < s.length; i++) {
    const last = out[out.length - 1];
    if (s[i][0] <= last[1]) last[1] = s[i][1];      // no Math.max
    else out.push(s[i].slice());
  }
  return out;
}
function mergeFixed(intervals) {
  const s = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [s[0].slice()];
  for (let i = 1; i < s.length; i++) {
    const last = out[out.length - 1];
    if (s[i][0] <= last[1]) last[1] = Math.max(last[1], s[i][1]);
    else out.push(s[i].slice());
  }
  return out;
}

const tricky = [[1, 10], [2, 3], [4, 5]];
console.log('broken:', JSON.stringify(mergeBroken(tricky)), '← lost the range');
console.log('fixed: ', JSON.stringify(mergeFixed(tricky)));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33function insert(intervals, newInterval) {
  const result = [];
  let [start, end] = newInterval;
  let i = 0;

  // Phase 1: everything that finishes before the new interval begins.
  while (i < intervals.length && intervals[i][1] < start) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: everything that overlaps gets absorbed into [start, end].
  while (i < intervals.length && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);

  // Phase 3: the rest, untouched.
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

console.log(insert([[1, 3], [6, 9]], [2, 5]));                       // [[1,5],[6,9]]
console.log(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]));  // [[1,2],[3,10],[12,16]]
console.log(insert([], [5, 7]));                                     // [[5,7]]
console.log(insert([[1, 5]], [2, 3]));                               // [[1,5]] swallowed
console.log(insert([[1, 5]], [6, 8]));                               // [[1,5],[6,8]] after
console.log(insert([[3, 5]], [1, 2]));                               // [[1,2],[3,5]] before

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

  // Sort by END. Keeping the earliest finisher leaves the most room after it.
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let kept = 1, lastEnd = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= lastEnd) { kept++; lastEnd = sorted[i][1]; }
  }
  return intervals.length - kept;
}

console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]));   // 1
console.log(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]));           // 2
console.log(eraseOverlapIntervals([[1, 2], [2, 3]]));                   // 0
console.log(eraseOverlapIntervals([]));                                 // 0

// Sorting by start gives the wrong answer on the first case.
function byStart(intervals) {
  const s = [...intervals].sort((a, b) => a[0] - b[0]);
  let kept = 1, lastEnd = s[0][1];
  for (let i = 1; i < s.length; i++) if (s[i][0] >= lastEnd) { kept++; lastEnd = s[i][1]; }
  return intervals.length - kept;
}
console.log('same input, sorted by start:', byStart([[1, 2], [2, 3], [3, 4], [1, 3]]), '← too many removed');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function maxConcurrent(intervals) {
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, +1]);      // something begins
    events.push([end, -1]);        // something ends
  }

  // Sort by time. On ties, process the -1 first: an interval ending at time t
  // frees up before one starting at t, under the half-open convention.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let active = 0, peak = 0, peakAt = null;
  for (const [time, delta] of events) {
    active += delta;
    if (active > peak) { peak = active; peakAt = time; }
  }
  return { peak, peakAt };
}

console.log(maxConcurrent([[0, 30], [5, 10], [15, 20]]));    // peak 2
console.log(maxConcurrent([[1, 5], [2, 6], [3, 7]]));        // peak 3 at time 3
console.log(maxConcurrent([[1, 2], [2, 3], [3, 4]]));        // peak 1, they only touch
console.log(maxConcurrent([[7, 10], [2, 4]]));               // peak 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37// Same idea without building event objects: sort starts and ends separately.
function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, peak = 0, e = 0;
  for (let s = 0; s < starts.length; s++) {
    // Release every room whose meeting ended before this one starts.
    while (e < ends.length && ends[e] <= starts[s]) { rooms--; e++; }
    rooms++;
    peak = Math.max(peak, rooms);
  }
  return peak;
}

console.log('rooms for [[0,30],[5,10],[15,20]]:', minMeetingRooms([[0, 30], [5, 10], [15, 20]]));
console.log('rooms for [[1,5],[2,6],[3,7]]:    ', minMeetingRooms([[1, 5], [2, 6], [3, 7]]));

// When the range of times is small and bounded, skip sorting entirely and
// bucket the deltas. This is a difference array.
function carPooling(trips, capacity) {
  const delta = new Array(1001).fill(0);
  for (const [passengers, from, to] of trips) {
    delta[from] += passengers;
    delta[to] -= passengers;
  }
  let onboard = 0;
  for (let stop = 0; stop < delta.length; stop++) {
    onboard += delta[stop];
    if (onboard > capacity) return false;
  }
  return true;
}

console.log('carPooling([[2,1,5],[3,3,7]], 4):', carPooling([[2, 1, 5], [3, 3, 7]], 4));   // false
console.log('carPooling([[2,1,5],[3,3,7]], 5):', carPooling([[2, 1, 5], [3, 3, 7]], 5));   // true
console.log('carPooling([[2,1,5],[3,5,7]], 3):', carPooling([[2, 1, 5], [3, 5, 7]], 3));   // true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function intervalIntersection(first, second) {
  const result = [];
  let i = 0, j = 0;

  while (i < first.length && j < second.length) {
    const lo = Math.max(first[i][0], second[j][0]);
    const hi = Math.min(first[i][1], second[j][1]);
    if (lo <= hi) result.push([lo, hi]);       // they genuinely overlap

    // Advance whichever interval finishes first — it cannot overlap anything else.
    if (first[i][1] < second[j][1]) i++;
    else j++;
  }
  return result;
}

const a = [[0, 2], [5, 10], [13, 23], [24, 25]];
const b = [[1, 5], [8, 12], [15, 24], [25, 26]];
console.log(intervalIntersection(a, b));       // [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
console.log(intervalIntersection([[1, 3], [5, 9]], []));    // []
console.log(intervalIntersection([[1, 7]], [[3, 10]]));     // [[3,7]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Calendar {
  constructor() { this.booked = []; }        // kept sorted by start

  book(start, end) {
    // Linear scan is fine for an interview; mention that a balanced tree or
    // binary search over starts would make this O(log n) per insert.
    for (const [s, e] of this.booked) {
      if (start < e && s < end) return false;   // clash
    }
    // Insert in the right position so the list stays sorted.
    let i = 0;
    while (i < this.booked.length && this.booked[i][0] < start) i++;
    this.booked.splice(i, 0, [start, end]);
    return true;
  }
}

const cal = new Calendar();
console.log('book [10,20]:', cal.book(10, 20));    // true
console.log('book [15,25]:', cal.book(15, 25));    // false, clashes
console.log('book [20,30]:', cal.book(20, 30));    // true, touching is fine
console.log('book [5,10]: ', cal.book(5, 10));     // true, before everything
console.log('calendar:', cal.booked);