Giao của hai danh sách khoảng trong C++

Giả sử chúng ta có hai danh sách các khoảng đóng, mỗi danh sách các khoảng là rời rạc từng cặp và được sắp xếp theo thứ tự. Chúng ta cần tìm giao của hai danh sách khoảng này.

Chúng ta biết rằng khoảng đóng [a, b] được ký hiệu là a ≤ b, tức là tập hợp các số thực x với a ≤ x ≤ b. Giao của hai khoảng đóng là một tập hợp số thực mà hoặc rỗng, hoặc có thể biểu diễn dưới dạng một khoảng đóng.

Ví dụ, nếu đầu vào là A = [[0,2],[5,10],[13,23],[24,25]] và B = [[1,5],[8,12],[15,24],[25,27]], thì đầu ra sẽ là [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Giải thuật

• Tạo danh sách kết quả res, đặt i := 0 và j := 0.
• Định nghĩa phương thức intersect() nhận hai khoảng a và b:
  • Nếu a[0] ≤ b[0] và a[1] ≥ b[0], trả về true.
  • Ngược lại, nếu b[0] ≤ a[0] và b[1] ≥ a[0], trả về true.
  • Trường hợp còn lại trả về false.
• Khi i < kích thước của A và j < kích thước của B:
  • Nếu intersect(A[i], B[j]):
    • temp := [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
    • A[i][0] := temp[1] + 1, B[j][0] := temp[1] + 1
    • Nếu A[i][0] > A[i][1] hoặc A[i][1] ≤ temp[0], tăng i lên 1.
    • Nếu B[j][0] > B[j][1] hoặc B[j][1] ≤ temp[0], tăng j lên 1.
    • Thêm temp vào kết quả.
    • Bỏ qua sang lần lặp tiếp theo.
  • Nếu A[i][0] > B[j][1], tăng j lên 1, ngược lại tăng i lên 1.

Ví dụ mã C++

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        while (i < A.size() && j < B.size()) {
            if (intersect(A[i], B[j])) {
                vector<int> temp = {max(A[i][0], B[j][0]), min(A[i][1], B[j][1])};
                A[i][0] = temp[1] + 1;
                B[j][0] = temp[1] + 1;
                if (A[i][0] > A[i][1] || A[i][1] <= temp[0]) i++;
                if (B[j][0] > B[j][1] || B[j][1] <= temp[0]) j++;
                result.push_back(temp);
                continue;
            }
            if (A[i][0] > B[j][1]) j++;
            else i++;
        }
        return result;
    }
    bool intersect(vector<int>& a, vector<int>& b) {
        if (a[0] <= b[0] && a[1] >= b[0]) return true;
        if (b[0] <= a[0] && b[1] >= a[0]) return true;
        return false;
    }
};

Đầu vào

[[0,2],[5,10],[13,23],[24,25]] [[1,5],[8,12],[15,24],[25,27]]

Đầu ra

[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]