การลบ Interval ที่ถูกครอบคลุมโดย Interval อื่นใน JavaScript

ปัญหา

ลบ intervals [a,b) ที่ถูกครอบคลุมโดย [c,d) (c <= a และ b <= d) คืนจำนวน intervals ที่เหลือ

ตัวอย่าง

arr = [[2,5], [5,7], [3,9]]
[5,7] ถูกครอบคลุมโดย [3,9] -> output: 2

ตัวอย่างโค้ด

const arr = [
  [2, 5],
  [5, 7],
  [3, 9]
];

const removeCovered = (arr = []) => {
  arr.sort(([a, b], [c, d]) => (a === c ? d - b : a - c));
  let last = arr[0];
  let count = arr.length;
  for (let i = 1; i < arr.length; i++) {
    const [a, b] = last;
    const [c, d] = arr[i];
    if (c >= a && d <= b) {
      count -= 1;
    } else {
      last = arr[i];
    }
  }
  return count;
};

console.log(removeCovered(arr));

ผลลัพธ์

2

คำอธิบาย

Sort by start ascending, end descending (start เท่ากัน ให้ end ใหญ่ก่อน)

เดินผ่าน: เก็บ last interval ที่ไม่ถูกลบ หาก current ถูกครอบคลุมโดย last -> count-- มิฉะนั้น update last

Time: O(n log n), Space: O(1) หรือ O(n) สำหรับ sort

LeetCode 1288 Remove Covered Intervals