Mô tả bài toán

Cho một khoảng thời gian tổng thể bắt đầu từ 1 đến $T$. Có $N$ nhân sự có thể được điều phối, trong đó mỗi nhân sự $i$ chỉ sẵn sàng làm việc trong một khoảng thời gian cố định $[S_i, E_i]$. Yêu cầu đặt ra là cần chọn ra số lượng nhân sự ít nhất sao cho tại mọi thời điểm $t \in [1, T]$, luôn có ít nhất một người đang làm việc.

Kết quả cần trả về:

• Nếu có thể phủ kín toàn bộ khoảng thời gian $[1, T]$, in ra số lượng nhân sự tối thiểu cần sử dụng.
• Nếu không tồn tại cách sắp xếp nào thỏa mãn, in ra -1.

Giới hạn dữ liệu

• 30% số test có: $1 \le N \le 100$
• 70% số test có: $1 \le N \le 1000$
• 100% số test có: $1 \le N \le 25000$, $1 \le T \le 1000000$, $1 \le S_i \le E_i \le T$

Ví dụ minh họa

Test case 1:

Dữ liệu vào:
3 10
1 7
3 6
8 10

Kết quả:
2

Test case 2:

Dữ liệu vào:
3 10
1 7
3 6
9 10

Kết quả:
-1

Phân tích và Giải thuật

Với giới hạn thời gian thực thi chặt chẽ và $N$ lên đến $25000$, thuật toán cần có độ phức tạp thời gian tối đa ở mức $O(N \log N)$. Bài toán này là một biến thể kinh điển của bài toán phủ đoạn (Interval Covering), có thể được giải quyết triệt để bằng phương pháp tham lam (Greedy Algorithm).

Chiến lược tham lam được xây dựng dựa trên việc ưu tiên các khoảng thời gian bắt đầu sớm nhất và kéo dài xa nhất có thể:

1. Sắp xếp dữ liệu: Chuẩn hóa danh sách các khoảng thời gian làm việc bằng cách sắp xếp theo thời điểm bắt đầu ($S_i$) tăng dần. Nếu hai khoảng thời gian có cùng điểm bắt đầu, thứ tự ưu tiên sẽ dựa trên thời điểm kết thúc ($E_i$).
2. Quét và chọn lựa:
   • Khởi tạo biến current_target = 1 đại diện cho mốc thời gian cần được phủ tiếp theo, và biến min_workers = 0 để đếm số nhân sự đã chọn.
   • Trong khi current_target <= T, thuật toán sẽ duyệt qua tất cả các nhân sự có thời điểm bắt đầu $S_i \le current\_target$. Trong nhóm các ứng viên thỏa mãn này, chọn ra người có thời điểm kết thúc $E_i$ lớn nhất (ký hiệu là furthest_end).
   • Nếu không tìm thấy bất kỳ ứng viên nào thỏa mãn (tức là furthest_end < current_target), điều này đồng nghĩa với việc xuất hiện một "lỗ hổng" thời gian không thể lấp đầy. Chương trình sẽ trả về -1 và kết thúc.
   • Ngược lại, tăng biến đếm min_workers lên 1 và cập nhật current_target = furthest_end + 1 để tiếp tục tìm kiếm người lấp đầy cho mốc thời gian kế tiếp.
3. Hoàn thành: Khi vòng lặp kết thúc và toàn bộ khoảng thời gian đã được phủ kín, trả về giá trị min_workers.

Mã nguồn triển khai

Dưới đây là mã nguồn C++ được tối ưu hóa về mặt cấu trúc dữ liệu và tốc độ đọc ghi I/O, sử dụng struct để biểu diễn các khoảng thời gian thay vì dùng std::pair.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct WorkShift {
    int start_time;
    int end_time;
};

bool compareShifts(const WorkShift& a, const WorkShift& b) {
    if (a.start_time != b.start_time) {
        return a.start_time < b.start_time;
    }
    return a.end_time < b.end_time;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int total_workers, total_duration;
    if (!(cin >> total_workers >> total_duration)) {
        return 0;
    }

    vector<WorkShift> shifts(total_workers);
    for (int i = 0; i < total_workers; ++i) {
        cin >> shifts[i].start_time >> shifts[i].end_time;
    }

    sort(shifts.begin(), shifts.end(), compareShifts);

    int current_target = 1;
    int min_workers = 0;
    int index = 0;

    while (current_target <= total_duration) {
        int furthest_end = -1;
        
        while (index < total_workers && shifts[index].start_time <= current_target) {
            furthest_end = max(furthest_end, shifts[index].end_time);
            index++;
        }

        if (furthest_end < current_target) {
            cout << -1 << "\n";
            return 0;
        }

        min_workers++;
        current_target = furthest_end + 1;
    }

    cout << min_workers << "\n";
    return 0;
}