Hướng dẫn giải: Phần Giao NhnHạn Lớn Nhất

Phân tích bài toán

Yêu cầu tìm độ dài phần giao nhau lớn nhất của các đoạn thẳng với \([A, B]\). Độ dài phần giao của đoạn thẳng \([L_i, R_i]\) với \([A, B]\) được tính bằng: \[\max\left(0, \min(R_i, B) - \max(L_i, A)\right)\] Với giới hạn của bài toán là \(N, Q \le 2000\), số lượng phép tính cho toàn bộ truy vấn chỉ khoảng \(2000 \times 2000 = 4 \cdot 10^6\) phép toán. Do đó, thuật toán tối ưu nhất là duyệt qua toàn bộ \(N\) đoạn thẳng đầu vào với mỗi truy vấn để tính độ dài phần giao và cập nhật giá trị cực đại trong \(O(N)\) thời gian cho mỗi truy vấn.

Độ phức tạp

• Thời gian: \(O(N)\) cho mỗi truy vấn, tổng thời gian \(O(N \cdot Q)\) cực kỳ nhanh và an toàn.
• Không gian: \(O(N)\) bộ nhớ.

Mã nguồn C++ mẫu

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<pair<int,int>> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].first >> intervals[i].second;
    }

    while (q--) {
        int a, b;
        cin >> a >> b;
        int max_overlap = -1;
        for (int i = 0; i < n; i++) {
            int overlap = min(intervals[i].second, b) - max(intervals[i].first, a);
            if (overlap >= 0) {
                max_overlap = max(max_overlap, overlap);
            }
        }
        cout << max_overlap << "\n";
    }
    return 0;
}