Sử dụng một multiset để tất cả lưu độ khó của công việc ~a_i~, với mỗi ~b_i~ ta tìm kiếm nhị phân trên multiset và bỏ phần tử lớn nhất thoả mãn điều kiện. Nếu multiset rỗng trước khi duyệt hết dãy ~b~ thì kết quả sẽ là ~-1~.

Độ phức tạp: ~O(NlogN)~

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e6+228;

int n, m, a[N], b[N];
multiset<int> s;
multiset<int>::iterator itr;

void solve()
{
    cin >> n >> m;
    for(int i=1; i<=n; ++i)
    {
        cin >> a[i];
        s.insert(a[i]);
    }
    for(int i=1; i<=m; ++i)
    {
        cin >> b[i];
        itr = s.upper_bound(b[i]);
        if(itr != s.begin())
        {
            --itr;
            s.erase(itr);
        }
    }
    if(s.empty()) cout << -1;
    else 
    {
        itr = s.end();
        --itr;
        cout << *itr;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}