ลบช่วงที่ถูกครอบคลุมใน C++

สมมติว่าเรามีรายการช่วง (intervals) เราต้องลบช่วงทั้งหมดที่ถูกครอบคลุมโดยช่วงอื่นในรายการ ช่วง [a,b) ถูกครอบคลุมโดย [c,d) ก็ต่อเมื่อ c <= a และ b <= d หลังจากนั้นคืนจำนวนช่วงที่เหลือ

ตัวอย่าง: [[1,4],[3,6],[2,8]] ผลลัพธ์: 2 เพราะ [3,6] ถูกครอบคลุมโดย [1,4] และ [2,8]

ขั้นตอนการแก้ปัญหา (Stack + Sorting)

• เรียงลำดับรายการช่วงตามเวลาสิ้นสุด (ending time)
• กำหนดสแต็ก st
• วนลูป i จาก 0 ถึง ขนาดของ a - 1
  • ถ้าสแต็กว่าง หรือ a[i] และช่วงบนสุดของสแต็กทับซ้อนกัน:
    • ใส่ a[i] เข้า st
  • อื่นๆ:
    • temp := a[i]
    • while สแต็กไม่ว่าง และ temp ทับซ้อนกับช่วงบนสุด:
      • ลบช่วงบนสุดออกจากสแต็ก
    • ใส่ temp เข้า st
• คืนขนาดของ st

ตัวอย่างโค้ด (C++)

#include <bits/stdc++.h> 
using namespace std; 

class Solution {
public:
    bool intersect(vector <int>& a, vector <int>& b) {
        return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
    }
    static bool cmp(vector <int> a, vector <int> b) {
        return a[1] < b[1];
    }
    void printVector(vector < vector <int> > a) {
        for(int i = 0; i < a.size(); i++) {
            cout << a[i][0] << " " << a[i][1] << endl;
        }
        cout << endl;
    }
    int removeCoveredIntervals(vector<vector<int>>& a) {
        sort(a.begin(), a.end(), cmp);
        stack < vector <int> > st;
        for(int i = 0; i < a.size(); i++) {
            if(st.empty() || !intersect(a[i], st.top())) {
                st.push(a[i]);
            } else {
                vector <int> temp = a[i];
                while(!st.empty() && intersect(temp, st.top())) {
                    st.pop();
                }
                st.push(temp);
            }
        }
        return st.size();
    }
};

int main() {
    vector<vector<int>> v = {{1,4},{3,6},{2,8}};
    Solution ob;
    cout << (ob.removeCoveredIntervals(v));
}

อินพุต

[[1,4],[3,6],[2,8]]

เอาต์พุต

2