ลบช่วงใน C++

สมมติว่าเรามีรายการช่วงที่เรียงลำดับและไม่ทับซ้อนกัน แต่ละช่วง intervals[i] = [a, b] แทนเซตของตัวเลข x ที่ a <= x < b เราต้องลบส่วนที่ทับซ้อนระหว่างช่วงใดช่วงหนึ่งใน intervals กับช่วง toBeRemoved แล้วคืนรายการช่วงที่เรียงลำดับหลังการลบ

ตัวอย่าง: [[0,2], [3,4],[5,7]], toBeRemoved := [1, 6] ผลลัพธ์: [[0, 1], [6,7]]

ขั้นตอนการแก้ปัญหา

• กำหนดเมธอด manipulate2(a, y):
  • x := แถวสุดท้ายของ a ลบแถวสุดท้ายออกจาก a
  • z := x
  • x[0] := y[1], z[1] := y[0]
  • ถ้า z[0] < z[1] ใส่ z เข้า a
  • ถ้า x[0] < x[1] ใส่ x เข้า a
• เมธอดหลักรับเมทริกซ์ in และอาร์เรย์ t:
  • กำหนดเมทริกซ์ ans, n := จำนวนแถวของ in
  • วนลูป i จาก 0 ถึง n-1:
    • ใส่ in[i] เข้า ans
    • a := แถวสุดท้ายของ ans, b := t
    • ถ้า a[0] > b[0] สลับ a และ b
    • ถ้า a และ b ทับซ้อน เรียก manipulate2(ans, t)
  • คืน ans

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

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

void print_vector(vector<vector<auto> > v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    bool isIntersect(vector <int> a, vector <int> b) {
        return max(a[0], a[1]) >= min(b[0], b[1]);
    }
    void manipulate2(vector < vector <int> > &a, vector <int> y) {
        vector <int> x = a.back();
        a.pop_back();
        vector <int> z = x;
        x[0] = y[1];
        z[1] = y[0];
        if(z[0] < z[1]) a.push_back(z);
        if(x[0] < x[1]) a.push_back(x);
    }
    vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
        vector < vector <int> > ans;
        int n = in.size();
        for(int i = 0; i < n; i++) {
            ans.push_back(in[i]);
            vector <int> a;
            vector <int> b;
            a = ans.back();
            b = t;
            if(a[0] > b[0]) swap(a, b);
            if(isIntersect(a, b)) {
                manipulate2(ans, t);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> v2 = {1,6};
    vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
    Solution ob;
    print_vector(ob.removeInterval(v1, v2));
}

อินพุต

[[0,2],[3,4],[5,7]] [1,6]

เอาต์พุต

[[0, 1, ],[6, 7, ],]