Here's the problem.
A client has to pay for the usage of a resource for a given timespan. However, the price is not flat. Depending on the amount of time used, the client can benefit from reductions (charge interval is 1h). Here's an example:
- One hour costs 1
- 5 hours costs costs 3
- One day (not necessarily 24h) costs at maximum 12
Depending on the start/end time, we should apply the rules that minimize the cost.
I think that creating a graph and applying a Dijkstra's Algorithm variant does the job (vertices representing timestamps and edges representing the cost).
dist = 0 for the start vertex and +inf for the rest
for v in topological order:
for u in neighbors[v] in reverse graph:
dist[v] = min(dist[v], dist[u] + weight(u, v))
The problem is that building the graph is really, really expensive. We have to build all the possible combination paths between start_time and end_time.
Is there a better approach to solve this problem?
EDIT:
Another possible way is identifying all the possible "charge slots". In the previois scenario, a usage between 20:00h and 06:00h (next day), would be:
- An unlimited number of charge slots of 60 mins at the cost of 1
- An unlimited number of charge slots of 300 mins at the cost of 3
- One charge slot of 240 min (20:00 -> 00:00h), at the cost of 12
- One charge slot of 360 min (00:00 -> 06:00h) at the cost of 12.
Now we have to minimize the cost, considering that the sum of charged slots must be >= total used minutes.
Are there any algorithm that can deal with this optimization problem?