Mã đề ucode : hotel-44771 - Điều kiện trl : AC Khách sạn UHotel có vô số phòng. Tuy nhiên, các phòng đã để rất lâu không dùng đến nên các phòng bám đầy bụi bẩn. UHotel bỗng nhận được N đơn đặt hàng, mỗi đơn đặt hàng là của một người khác muốn thuê phòng bất kỳ trong thời gian [Si, Ei). Tất nhiên là mỗi phòng chỉ được có một người khách ở vào thời điểm nào đó. Giờ UHotel muốn dùng một phòng nào đó cho khách ở thì phải mua nội thất cho phòng đó (sau khi mua nội thất thì phòng đó sẽ không phải mua nội thất lại nữa) tốn rất nhiều tiền nên UHotel muốn hỏi bạn xem, cần mua nội thất cho ít nhất bao nhiêu phòng để phục vụ toàn bộ số khác trên. Mô tả đầu vào Dòng đầu chứa số N. N dòng sau, mỗi dòng chứa hai số Si và Ei. Ràng buộc 1 Si < Ei 109 N 105 Mô tả đầu ra Số phòng ít nhất cần mua nội thất. Test case mẫu Đầu vào mẫu 1 2 1 2 3 4 Đầu ra mẫu 1 1 Đầu vào mẫu 2 2 1 3 2 3 Đầu ra mẫu 2 2 NL : top những thứ ức chế nhất :v

Thuật toán

Ta sẽ đánh dấu mỗi thời điểm một người chuyển vào ($s_i$) là một dấu ngoặc mở, và thời điểm một người chuyển ra ($e_i$) là một dấu ngoặc đóng. Gọi mỗi thời điểm được đánh dấu là thời điểm quan trọng Sau đó, ta sẽ tạo một xâu ngoặc dựa trên $2N$ thời điểm khách ra và vào theo cơ chế như sau:

- Thời điểm quan trọng nào xảy ra trước thì viết dấu ngoặc tương ứng với thời điểm đó trước

- Nếu có nhiều hơn hoặc bằng hai sự kiện (khách ra/vào) xảy ra trong cùng một thời điểm quan trọng, dấu ngoặc đóng luôn đứng trước dấu ngoặc mở. Nếu dấu ngoặc tương ứng của hai thời điểm giống nhau thì viết thế nào cũng được.

Ví dụ, với test mẫu thứ 2, ta sẽ đánh dấu từng thời điểm với dấu ngoặc tương ứng như sau

$\begin{array}{cccc}\text{Thời điểm}&1&2&3\\&(&(&))\end{array}$

Do đó, dãy ngoặc cho test thứ 2 là (())

Dễ thấy, dãy ngoặc được sinh ra luôn là dãy ngoặc đúng. 

Bài toán của chúng ta thực chất là tìm xem có nhiều nhất bao nhiêu người cùng ở trong cùng một thời điểm. Dễ thấy, ta cần có $2N$ thời điểm cần quan tâm, và các thời điểm đó chính là các thời điểm quan trọng.

Gọi $b_i$ và $c_i$ lần lượt là số ngoặc mở và ngoặc đóng đến ký tự thứ $i$ trong dãy ngoặc tạo được. Ta thấy trong thời điểm quan trọng thứ $i$, có $b_i - c_i$ khách đang ở trong khách sạn cùng một lúc. Do đó đáp án của chúng ta sẽ là $max(b_1-c_1, b_2-c_2, \ldots, b_{2N} - c_{2N}$

Do bài này kiếm được tới 1100 ucoin trên ucode nên mình sẽ để việc code là thử thách cho bạn. Một phần code của mình ở bên dưới cho bạn tham khảo.

#include <bits/stdc++.h>
#define ll long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
int main() {
    ios
    ll n;
    cin>>n;
    vector<pair<ll,ll>>a;
    for(int i=0;i<n;i++)
    {
        ll p,d;
        cin>>p>>d;
        a.push_back(make_pair(p,1));
        a.push_back(make_pair(d,-1));
    }
    sort(a.begin(),a.end());
    ll m=0;
    ll l=0;
    for(const auto&c:a)
    {
        l+=c.second;
        m=max(m,l);
    }
    cout<<m ;
    return 0;
}