Giả sử chúng ta có một danh sách đã sắp xếp gồm các khoảng rời nhau, mỗi khoảng [i] =[a, b] biểu diễn tập hợp các số x sao cho a <=x
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một phương thức có tên là sports2 (), phương thức này sẽ nhận ma trận a và một mảng y
- x:=hàng cuối cùng của ma trận a, sau đó xóa hàng cuối cùng khỏi a
- z:=x
- x [0]:=y [1], z [1]:=y [0]
- nếu z [0] - z [1], sau đó chèn z vào một
- nếu x [0] - x [1], thì hãy chèn x vào một
- Phương thức chính sẽ đưa ma trận vào và một mảng t
- xác định một ma trận ans và n:=số hàng trong ma trận trong
- cho tôi trong phạm vi từ 0 đến n -
- chèn [i] vào ans
- a:=hàng cuối cùng của a, b:=t
- nếu a [0]> b [0], thì hoán đổi a và b
- nếu a và b giao nhau, thì gọi Thao tác 2 (ans, t)
- trả lại ans
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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; } }; main(){ vector<int> v2 = {1,6}; vector<vector<int>> v1 = {{0,2},{3,4},{5,7}}; Solution ob; print_vector(ob.removeInterval(v1, v2)); }
Đầu vào
[[0,2],[3,4],[5,7]] [1,6]
Đầu ra
[[0, 1, ],[6, 7, ],]