let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

NKREZ - Hội trường

solution.md

Sử dụng tìm kiếm nhị phân kết hợp với quy hoạch động. Đầu tiên ta sắp lại các yêu cầu theo thời gian kết thúc tăng dần. Đặt \(F[i]\) là thời gian lớn nhất có thể cho thuê khi chọn trong các yêu cầu từ \(A[1]\) đến \(A[i]\).

  • Khi không chọn \(A[i]\), ta có \(F[i] = F[i-1]\).
  • Khi chọn \(A[i]\), ta có \(F[i] = (A[i].end-A[i].start) + F[j]\), với \(j\) lớn nhất thỏa \(A[j]\) không bị trùng giờ với \(A[i]\), tức là \(A[j].end \leq A[i].start\).
main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Time { int start, end; };
#define val(x) ((x).end-(x).start)
bool operator < (const Time &a, const Time &b) {
    return a.end < b.end;
}

int bs(const vector<Time> &a, int l, int r, int val) {
    while (l<=r) {
        int k = (l+r) / 2;
        if (a[k].end <= val) l = k+1;
        else r = k-1;
    }
    return r;
}

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

    int n; cin >> n;
    vector<Time> a(n);
    for (auto &x: a) cin >> x.start >> x.end;

    sort(a.begin(), a.end());

    vector<int> f(n);
    f[0] = val(a[0]);
    for (int i=1; i<n; i++) {
        int j = bs(a, 0, i-1, a[i].start);
        f[i] = max(f[i-1], val(a[i]) + (j>=0? f[j]:0));
    }
    cout << f[n-1];
    return 0;
}
Comments