algorithm - Finding the minimum cost at each point in time from a set of weighted intervals - Stack Overflow

admin管理员组

文章数量:1391991

Let’s say we have a list of intervals, each of which has a cost associated with it. Assume that there is always at least one interval active. The solution would be a timeline of non overlapping intervals with the minimum cost at any point in time.

For example, for a list intervals of the type [start, end, value]

[
    [2024-01-01, 2024-05-01, 500],
    [2024-01-01, 2024-03-01, 400],
    [2024-02-01, 2024-04-01, 300],
    [2024-03-01, 2024-04-01, 200]
]

Then the solution would be

[   
    [2024-01-01, 2024-02-01, 400],
    [2024-02-01, 2024-03-01, 300],
    [2024-03-01, 2024-04-01, 200],
    [2024-04-01, 2024-05-01, 500]
]

I do have a variant of the sweeping line algorithm, although I am not sure it is the best way to solve this problem. In that solution, I have to iterate through each start and end point of every interval (in order), keep track of the active intervals, and at each point, choose the minimum cost among them. This runs in O(n^2).

Edit: @pjs gave me an idea of using a priority queue. This will be give us a better time complexity for choosing the minimum cost at each point. This will run in O(n log(n)).

I am wondering if there is any other algorithms for this? I’ve looked into scheduling algorithms but these do not seem to fit my problem exactly.

本文标签： algorithmFinding the minimum cost at each point in time from a set of weighted intervalsStack Overflow