Tuyên bố miễn trừ trách nhiệm: Phương pháp được mô tả bên dưới không phổ biến nhưng thường có thể giải quyết vấn đề hoặc giúp bạn tìm ra giải pháp phù hợp.
Nếu có một tập hợp các khoảng trống nằm trên một số trục (thường là trục thời gian hoặc chỉ số của một số mảng) và bạn cần chọn một số trong số chúng theo cách tối ưu để các khoảng trống đã chọn không giao nhau, thì bạn nên thử sử dụng lập trình động .
Sơ đồ giải pháp gần đúng:
Ban đầu, chúng tôi sắp xếp các khoảng trống có sẵn theo đường viền bên phải. Hãy bắt đầu động lực học sau: dp[i] - câu trả lời cho khoảng i đầu tiên.
Ta sẽ tính lại như sau: đầu tiên xét trường hợp khoảng này sẽ không được sử dụng, khi đó chỉ cần dp[i] = dp[i-1]. Lưu ý rằng điều này đảm bảo rằng các giá trị của dp[i] không giảm khi tôi lớn lên. Và điều này là hợp lý, bởi vì. thêm một khoảng cách mới, chúng ta không thể làm xấu đi câu trả lời toàn cầu: hoặc chúng ta đơn giản bỏ qua khoảng cách mới hoặc chúng ta xây dựng một biến thể có lợi hơn bằng cách sử dụng nó. Bây giờ, nếu chúng ta muốn sử dụng khoảng cách thứ i, thì chúng ta có thể sử dụng những khoảng trống có đường viền bên phải nhỏ hơn đường viền bên trái của khoảng cách hiện tại, vì chúng ta phải chọn một tập hợp các khoảng trống không chồng lấp. Để làm điều này, ban đầu chúng tôi đã sắp xếp các khoảng trống theo đường viền bên phải, để bây giờ chúng tôi có thể tìm thấy vị trí cần thiết một cách hiệu quả. Điều này có thể được thực hiện một cách phân tích, nếu có thể, nhưng trong trường hợp chung, có thể tìm thấy một khoảng cách với một binsearch, đường viền bên phải nhỏ hơn đường viền bên trái của đường viền hiện tại, đồng thời, mức tối đa có thể một. Chúng tôi muốn tối đa hóa đường viền bên phải vì lý do tham lam, bởi vì khi tôi lớn lên, câu trả lời chỉ có thể tăng lên. Theo đó, chúng ta tìm vị trí p cần thiết và tính toán lại từ dp[i] đến dp[p] và khoảng thứ i.