\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Xét bài toán con, với một khoảng delay time nhất định. Thì tối đa bao nhiêu máy bay có thể hạ cánh với một đường băng

• Tiếp cận tham lam, ta chọn đường băng hợp lí nhất để hạ cánh máy bay nếu có thể. Từ đó tìm ra P máy bay tối đa hạ cánh được

• Chặt nhị phân cho truy vấn 2 để tìm delay time tối đa sao cho đủ P máy bay hạ cánh

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Vì ta chỉ quan tâm thơi gian máy bay đậu chứ không phải thứ tự máy bay theo danh sách nên ta sẽ sắp xếp chúng theo thời gian hạ cánh sớm nhất đến hạ cánh muộn nhất

• Để tính xem với độ trễ delay_time thì tối đa bao nhiêu máy bay có thể hạ cánh, ta sẽ dùng thuật toán tham lam như sau:

Ta sẽ tạo ra một tập các đường băng để chứa máy bay, gồm có giá trị là thời gian nhỏ nhất để có thể tiếp nhận thêm được một máy bay khác vào đương băng đó

Khi xử lí từng máy bay ta tính được thời gian nhỏ nhất cần để nó xuất phất, đó là đường băng có độ trễ nhỏ nhất kết hợp với thời gian trễ hạn delay_time

Kiểm tra nếu thời gian hạ cánh muộn nhất của nó vẫn chưa quá hạn thì ta sẽ cho chuyến bay đó cất cánh, đồng thời tăng biến đếm kết quả và cập nhật độ trễ đường băng đó

• Có được số lượng máy bay đó là max_count, để tìm được độ trễ nhỏ nhất, ta sẽ chặt nhị phân:

Xét trong khoảng từ thời gian trễ ban đầu tới dương vô cùng.

Ta chặt tới thời gian trễ lớn nhất max_delay mà số lượng máy bay hạ cánh được với độ trễ này vẫn bằng max_count

Nhớ cẩn thận xuất \(-1\) khi chỉ có 1 máy bay hạ cánh được

\(\color{purple}{\text{Độ phức tạp}}\)

• Truy vấn 1:

Dùng trâu duyệt toàn bộ cách mất \(O(f(x)) = O(\frac{n!}{m! \times (n - m)!})\)

Dùng quy hoạch động để tăng tốc độ duyệt mất \(O(f(x)) = O(n \times m)\)

Dùng thuật toán tham lam để tìm đường băng trễ nhỏ nhất mất \(O(f(x)) = O(n \times m)\)

Dùng thuật toán tham lam kết hợp cấu trúc dữ liệu heap để tìm mất \(O(f(x)) = O((n + m) \times log(m))\)

• Truy vấn 2:

Duyệt trâu qua các giá trị mất \(O(g(x)) = O(max(landing\_time) \times f(x))\)

Dùng chặt nhị phân mất \(O(g(x)) = O(log(max(landing\_time)) \times f(x))\)

• Tổng cộng độ phức tạp bài toán là: \(O(f(x)) + O(g(x))\)

\(\color{brown}{\text{Giải thích biến}}\)

• Số lượng hạ cánh: \(number\_of\_landing\)

• Số lượng đường băng: \(number\_of\_runway\)

• Thời gian giãn cách: \(flight\_delay\)

• Kiểu dữ liệu hạ cánh: \(landing\_type\)

Thời gian hạ cánh sớm nhất: \(min\_time\)

Thời gian hạ cánh muộn nhất: \(max\_time\)

Phép so sánh hai lần hạ cánh: Ưu tiên (\(min\_time\)) nhỏ nhất \(\rightarrow\) (\(max\_time\)) nhỏ nhất

• Danh sách các lần hạ cánh: \(Landing\_list\)

• Máy bay hiện tại: \(current\_plane\)

\(\color{green}{\text{Code tham khảo }}\): Tham lam, Chặt nhị phân, Cấu trúc dữ liệu đặc biệt (Heap)

\(^{^{\color{purple}{\text{Độ phức tạp : }} O((n + m) \times log(m) \times log(max(time)))\ \color{purple}{\text{thời gian}}\ ||\ O(n + m)\ \color{purple}{\text{bộ nhớ}}}}\)

/// A plane :D
struct landing_type
{
    int min_time = 0;
    int max_time = 0;
    bool operator < (landing_type other)
    {
        return (min_time != other.min_time) ? (min_time < other.min_time)
                                            : (max_time < other.max_time);
    }
};

int number_of_landing, number_of_runway, flight_delay;
vector<landing_type> Landing_list;

/// Count maximum possible amount of Landing_list
/// Where no 2 consecutive Landing_list (flight_delay) < (delay_time)
int solve(int delay_time)
{
    /// Construct runways, initially all are ready without cost
    priority_queue<int, vector<int>, greater<int> > Runway_list;
    for (int i = 1; i <= number_of_runway; ++i) Runway_list.push(-delay_time);

    /// Counting valid planes
    int res = 0;
    for (landing_type current_plane : Landing_list)
    {
        /// The smallest possible time for a plane to land on any runway
        int min_start_time = Runway_list.top() + delay_time;

        /// This plan is valid, it will land right now
        if (current_plane.max_time >= min_start_time)
        {
            /// One more valid plane
            res++;

            /// Update new runway, with next smallest valid time
            Runway_list.pop();
            Runway_list.push(max(min_start_time, current_plane.min_time));
        }
    }

    /// Ofcourse let return the result
    return res;
}

int main()
{
    /// Input part
    cin >> number_of_landing >> number_of_runway >> flight_delay;

    Landing_list.resize(number_of_landing);
    for (landing_type &current_plane : Landing_list)
    {
        cin >> current_plane.min_time;
        cin >> current_plane.max_time;
    }
    sort(all(Landing_list));

    int max_count = solve(flight_delay);
    if (max_count == 1) /// There is no delay for one plane
    {
        cout << max_count << ' ' << -1;
        return 0;
    }

    /// Binary search approach | O((n + current_delay) log current_delay * log n)
    /// There is no (solve(x) > max_count) case since (max_count) is upper_limit
    /// While (flight_delay) <= (lower_delay) <= optimal(current_delay) <= (upper_delay) <= +INF
    /// --- if (solve(current_delay) = max_count) we can still delay more, so (lower_delay) = (current_delay) + 1
    ///                                                              and update (max_delay) = (current_delay)
    /// --- if (solve(current_delay) < max_count) we cant delay anymore,   so (upper_delay) = (current_delay) - 1

    /// Find maximum delay time without changing the count
    int max_delay = flight_delay;
    for (int lower_delay = flight_delay, upper_delay = +INF; lower_delay <= upper_delay; )
    {
        /// Binary search
        int current_delay = (lower_delay + upper_delay) / 2;
        int current_count = solve(current_delay);

        /// This delay is valid
        if (current_count == max_count)
        {
            max_delay = current_delay;
            lower_delay = current_delay + 1;
        }
        else /// No, let reduce the delay time
        {
            upper_delay = current_delay - 1;
        }
    }

    /// Output part
    cout << max_count << ' ' << max_delay;
    return 0;
}