// ─────────────────────────────────────────────────────────────────────────────
// INTERVALS
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : [start, end] pairs; almost always sort first, then sweep once.
// TELL   : "intervals", "meetings", "overlap", "merge", "rooms", "schedule", "balloons / arrows",
//          "free time", "busy", "non-overlapping".
// SAY    : sort by start (merging), sort by end (greedy max non-overlapping), sweep line, overlap test
//          a.start <= b.end && b.start <= a.end, min-heap of end times, two-pointer over starts/ends.
// BIG-O  : O(n log n) for the sort; sweep is O(n). Heap variants O(n log n).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

const byStart = (a, b) => a[0] - b[0];
const byEnd = (a, b) => a[1] - b[1];
const overlaps = (a, b) => a[0] <= b[1] && b[0] <= a[1]; // closed intervals; use < for half-open
assert.equal(overlaps([1, 3], [3, 5]), true);
assert.equal(overlaps([1, 2], [3, 4]), false);

// ── 1. Merge intervals  —  sort by start; if cur.start <= last.end extend last.end  —  O(n log n) / O(n)
function merge(intervals) {
  const out = [];
  for (const [s, e] of [...intervals].sort(byStart)) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s, e]);
  }
  return out;
}
assert.deepEqual(merge([[1, 3], [2, 6], [8, 10], [15, 18]]), [[1, 6], [8, 10], [15, 18]]);
assert.deepEqual(merge([[1, 4], [2, 3]]), [[1, 4]]); // contained
assert.deepEqual(merge([]), []);

// ── 2. Insert interval (input sorted, non-overlapping)  —  add all ending before; merge all overlapping; add the rest  —  O(n) / O(n)
function insert(intervals, newI) {
  const out = [];
  let i = 0;
  const n = intervals.length;
  while (i < n && intervals[i][1] < newI[0]) out.push(intervals[i++]);
  while (i < n && intervals[i][0] <= newI[1]) {
    newI = [Math.min(newI[0], intervals[i][0]), Math.max(newI[1], intervals[i][1])];
    i++;
  }
  out.push(newI);
  while (i < n) out.push(intervals[i++]);
  return out;
}
assert.deepEqual(insert([[1, 3], [6, 9]], [2, 5]), [[1, 5], [6, 9]]);
assert.deepEqual(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]), [[1, 2], [3, 10], [12, 16]]);
assert.deepEqual(insert([], [5, 7]), [[5, 7]]);

// ── 3. Non-overlapping intervals (min removals)  —  sort by END; keep interval if start >= lastEnd; removals = n - kept  —  O(n log n)
//        SAY: "greedy by earliest end time leaves the most room; classic activity selection."
function eraseOverlapIntervals(intervals) {
  let kept = 0, lastEnd = -Infinity;
  for (const [s, e] of [...intervals].sort(byEnd)) if (s >= lastEnd) { kept++; lastEnd = e; }
  return intervals.length - kept;
}
assert.equal(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]), 1);
assert.equal(eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]), 2);
assert.equal(eraseOverlapIntervals([]), 0);

// ── 4. Meeting rooms I (can attend all?)  —  sort by start; any start < previous end => conflict  —  O(n log n)
function canAttendMeetings(intervals) {
  const s = [...intervals].sort(byStart);
  for (let i = 1; i < s.length; i++) if (s[i][0] < s[i - 1][1]) return false;
  return true;
}
assert.equal(canAttendMeetings([[0, 30], [5, 10], [15, 20]]), false);
assert.equal(canAttendMeetings([[7, 10], [2, 4]]), true);
assert.equal(canAttendMeetings([]), true);

// ── 5. Meeting rooms II (min rooms), two-pointer  —  sort starts and ends separately; start < end[j] => new room else reuse  —  O(n log n) / O(n)
function minMeetingRooms(intervals) {
  const starts = intervals.map((x) => x[0]).sort((a, b) => a - b);
  const ends = intervals.map((x) => x[1]).sort((a, b) => a - b);
  let rooms = 0, j = 0;
  for (const s of starts) {
    if (s < ends[j]) rooms++; // a meeting is still running
    else j++; // one ended; reuse its room
  }
  return rooms;
}
assert.equal(minMeetingRooms([[0, 30], [5, 10], [15, 20]]), 2);
assert.equal(minMeetingRooms([[7, 10], [2, 4]]), 1);
assert.equal(minMeetingRooms([]), 0);

// ── 6. Meeting rooms II, heap version  —  sort by start; min-heap of end times; pop if earliest end <= start; size = rooms  —  O(n log n)
function minMeetingRoomsHeap(intervals) {
  const ends = []; // tiny min-heap on numbers
  const push = (x) => { ends.push(x); for (let i = ends.length - 1, p; i > 0 && ends[p = (i - 1) >> 1] > ends[i]; i = p) [ends[i], ends[p]] = [ends[p], ends[i]]; };
  const pop = () => {
    const top = ends[0], last = ends.pop();
    if (ends.length) { ends[0] = last; for (let i = 0;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < ends.length && ends[l] < ends[m]) m = l; if (r < ends.length && ends[r] < ends[m]) m = r; if (m === i) break; [ends[i], ends[m]] = [ends[m], ends[i]]; i = m; } }
    return top;
  };
  for (const [s, e] of [...intervals].sort(byStart)) { if (ends.length && ends[0] <= s) pop(); push(e); }
  return ends.length;
}
assert.equal(minMeetingRoomsHeap([[0, 30], [5, 10], [15, 20]]), 2);
assert.equal(minMeetingRoomsHeap([[1, 5], [2, 6], [3, 7], [8, 9]]), 3);
assert.equal(minMeetingRoomsHeap([]), 0);

// ── 7. Minimum arrows to burst balloons  —  sort by END; new arrow when start > lastArrowPos  —  O(n log n)
function findMinArrowShots(points) {
  if (points.length === 0) return 0;
  let arrows = 1, pos = null;
  for (const [s, e] of [...points].sort(byEnd)) {
    if (pos === null || s > pos) { arrows += pos === null ? 0 : 1; pos = e; }
  }
  return arrows;
}
assert.equal(findMinArrowShots([[10, 16], [2, 8], [1, 6], [7, 12]]), 2);
assert.equal(findMinArrowShots([[1, 2], [3, 4], [5, 6], [7, 8]]), 4);
assert.equal(findMinArrowShots([[1, 2], [2, 3], [3, 4], [4, 5]]), 2);

// ── 8. Interval list intersections (two sorted lists)  —  two pointers; lo = max starts, hi = min ends; advance the one ending first  —  O(n + m)
function intervalIntersection(A, B) {
  const out = [];
  let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    const lo = Math.max(A[i][0], B[j][0]), hi = Math.min(A[i][1], B[j][1]);
    if (lo <= hi) out.push([lo, hi]);
    if (A[i][1] < B[j][1]) i++; else j++;
  }
  return out;
}
assert.deepEqual(intervalIntersection([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]]), [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]);
assert.deepEqual(intervalIntersection([[1, 3]], [[4, 5]]), []);
assert.deepEqual(intervalIntersection([], [[1, 2]]), []);

// ── 9. Employee free time sketch  —  flatten all schedules, sort by start, merge; gaps between merged blocks = free  —  O(n log n)
function employeeFreeTime(schedule) {
  const merged = merge(schedule.flat());
  const out = [];
  for (let i = 1; i < merged.length; i++) out.push([merged[i - 1][1], merged[i][0]]);
  return out;
}
assert.deepEqual(employeeFreeTime([[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]), [[3, 4]]);
assert.deepEqual(employeeFreeTime([[[1, 3], [6, 7]], [[2, 4]], [[2, 5], [9, 12]]]), [[5, 6], [7, 9]]);
assert.deepEqual(employeeFreeTime([[[1, 2]]]), []);

// ── 10. Sort-by-start vs sort-by-end heuristic
//   sort by START : merging, inserting, "is there any overlap", sweeping rooms/resources (what is open right now).
//   sort by END   : greedy selection of the MAX number of non-overlapping intervals (activity selection), min arrows,
//                   min removals. Picking the earliest finishing interval never hurts (exchange argument).
//   Both          : rooms II two-pointer sorts starts and ends independently.
const activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
assert.equal(activities.length - eraseOverlapIntervals(activities), 4); // max non-overlapping = 4

console.log('ok: algorithms/intervals.js');