Insert Interval ใน C++

สมมติว่าเรามีชุดของช่วงที่ไม่ทับซ้อนกัน เราต้องแทรกช่วงใหม่เข้าไปในช่วงเหล่านั้น สามารถรวมช่วงได้หากจำเป็น เช่นถ้าอินพุตคือ [[1,4],[6,9]] และช่วงใหม่คือ [2,5] ผลลัพธ์จะเป็น [[1,5],[6,9]]

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

• แทรกช่วงใหม่ลงท้ายรายการช่วงเดิม
• เรียงลำดับรายการช่วงตามเวลาเริ่มต้นของช่วง n := จำนวนช่วง
• สร้างอาร์เรย์ ans ใส่ช่วงแรกลงใน ans
• index := 1
• while index < n
  • last := ขนาดของ ans – 1
  • ถ้าค่าสูงสุดของ ans[last, 0] และ ans[last, 1] < ค่าต่ำสุดของ intervals[index, 0], intervals[index, 1] ใส่ intervals[index] ลง ans
  • มิฉะนั้น
    • ตั้งค่า ans[last, 0] := min ของ ans[last, 0], intervals[index, 0]
    • ตั้งค่า ans[last, 1] := max ของ ans[last, 1], intervals[index, 1]
  • เพิ่ม index ขึ้น 1
• คืนค่า ans

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

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

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

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:
    static bool cmp(vector<int> a, vector<int> b){
        return a[0] < b[0];
    }
    vector<vector<int>> insert(vector<vector<int> >& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        vector<vector<int>> ans;
        ans.push_back(intervals[0]);
        int index = 1;
        while(index < n){
            int last = ans.size() - 1;
            if(max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1])){
                ans.push_back(intervals[index]);
            } else {
                ans[last][0] = min(ans[last][0], intervals[index][0]);
                ans[last][1] = max(ans[last][1], intervals[index][1]);
            }
            index++;
        }
        return ans;
    }
};

int main(){
    vector<vector<int>> v = {{1,4},{6,9}};
    vector<int> v1 = {2,5};
    Solution ob;
    print_vector(ob.insert(v, v1));
}

อินพุต

[[1,4],[6,9]] [2,5]

เอาต์พุต

[[1, 5, ],[6, 9, ],]