Hướng giải của Đoạn phủ dày nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Sử dụng kỹ thuật sweep line kết hợp nén tọa độ. Với mỗi đoạn [l, r], tạo sự kiện +1 tại l và -1 tại r+1. Nén tất cả các tọa độ, sắp xếp, duyệt và cập nhật biến đếm, lấy giá trị lớn nhất.

Độ phức tạp: O(N log N) thời gian, O(N) bộ nhớ.

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    map<int, int> diff;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }

    int cur = 0, ans = 0;
    for (auto [coord, val] : diff) {
        cur += val;
        if (cur > ans) ans = cur;
    }
    cout << ans << '\n';
    return 0;
}

Python

import sys
from collections import defaultdict

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))

    diff = defaultdict(int)
    for _ in range(n):
        l = int(next(it))
        r = int(next(it))
        diff[l] += 1
        diff[r + 1] -= 1

    cur = 0
    ans = 0
    for coord in sorted(diff):
        cur += diff[coord]
        if cur > ans:
            ans = cur
    print(ans)

if __name__ == '__main__':
    main()

Nhận xét

Không có ý kiến tại thời điểm này.