Bước 1: Sắp xếp dự án Sắp xếp các dự án theo ngày kết thúc tăng dần. Bước 2: Định nghĩa DP dp[i] = tổng tiền tối đa khi xét các dự án từ 1 đến i, và có thể chọn hoặc không chọn dự án i Công thức: dp[i] = max( dp[i-1], :không chọn dự án i dp[j] + p[i] :chọn dự án i ) Trong đó: j là dự án gần nhất trước i mà không giao với i Tức là b[j] < a[i] Nếu không có thì dp[j] = 0 Bước 3: Tìm j bằng binary search Vì đã sắp xếp theo b[i], ta có thể: Lưu mảng end[i] = b[i] Với mỗi i, tìm j lớn nhất sao cho: end[j] < a[i] Dùng upper_bound để làm trong O(log n).