Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

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

Chọn các dự án không chồng lấn để đạt tổng phần thưởng lớn nhất.

Bạn sẽ học được gì

  • Sắp xếp khoảng theo thời điểm kết thúc
  • Tìm dự án tương thích gần nhất bằng tìm kiếm nhị phân
  • Chọn giữa nhận hoặc bỏ một dự án

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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;

Giải thích

Hai dự án đầu tiên có tổng phần thưởng là 9. Dự án cuối cùng có phần thưởng 10 và bị xung đột với cả hai dự án trước, nên chọn riêng dự án này.

Ví dụ 2
Đầ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;

Giải thích

Cả hai dự án đều chiếm ngày 2. Chỉ chọn dự án thứ hai với phần thưởng 5.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đây là bài toán weighted interval scheduling với các khoảng thời gian chồng lấn.

Gợi ý 2

Sắp xếp dự án theo ngày kết thúc và ghép mỗi dự án với dự án trước đó gần nhất còn tương thích.

Gợi ý 3

Phải xác định rõ xung đột: dự án khác bắt đầu đúng vào ngày kết thúc vẫn bị chồng lấn.

Độ phức tạp mong đợi

thời gian O(n log n), bộ nhớ phụ O(n)

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 800 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.