Phần Thưởng Dự Án Tối Đa

Mỗi dự án được biểu diễn bởi [start_day, end_day, reward]. Dự án chiếm tất cả các ngày từ start_day đến end_day, bao gồm cả hai ngày này. Bạn chỉ có thể tham gia một dự án trong một ngày. Hãy chọn một tập con các dự án sao cho tổng phần thưởng là lớn nhất. Một dự án bắt đầu vào đúng ngày kết thúc của dự án khác cũng được coi là xung đột với dự án đó.

Cài đặt hàm project_rewards(projects).

Đầu vào

projects: Mỗi dòng gồm ba số nguyên: ngày bắt đầu, ngày kết thúc và phần thưởng.

Đầu ra

Trả về tổng phần thưởng lớn nhất; không cần trả về các dự án đã chọn.

Ràng buộc

1 ≤ projects ≤ 200.000. 1 ≤ start_day ≤ end_day ≤ 1.000.000.000. Phần thưởng là số nguyên dương không quá 1.000.000.000.

Ví dụ

Đầu vào:
projects = [
    [1, 2, 4],
    [3, 4, 5],
    [2, 3, 10]
]

Kết quả mong đợi:
expected = 10

Đầu vào:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {3, 4, 5},
    {2, 3, 10}
};

Kết quả mong đợi:
long long expected = 10;

Đầu vào:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {3, 4, 5},
    new long[] {2, 3, 10}
};

Kết quả mong đợi:
long expected = 10;

Đầu vào:
projects = [
    [1, 2, 4],
    [2, 3, 5]
]

Kết quả mong đợi:
expected = 5

Đầu vào:
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {2, 3, 5}
};

Kết quả mong đợi:
long long expected = 5;

Đầu vào:
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 5}
};

Kết quả mong đợi:
long expected = 5;

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

• Projects — 1140