patternMinor
Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?
Viewed 0 times
cantemperaturesettempbuyingrangesfewestheuristicthatfor
Problem
We have a set of $n$ products, each $i$th product can be kept in a
temperature between $c_i$ and $h_i$.
We have to buy fewest number of fridges for these products. The
fridges can only have a fixed temperature.
For me I think of this problem as intervals of product temperatures that are placed on the axis.
My idea to solve it is to see which product's temperature range overlaps with most other products temperature ranges, then we can place these products in one fridge.
But the algorithm for this would be inefficient..
What's a simple greedy solution for this? any ideas?
temperature between $c_i$ and $h_i$.
We have to buy fewest number of fridges for these products. The
fridges can only have a fixed temperature.
For me I think of this problem as intervals of product temperatures that are placed on the axis.
My idea to solve it is to see which product's temperature range overlaps with most other products temperature ranges, then we can place these products in one fridge.
But the algorithm for this would be inefficient..
What's a simple greedy solution for this? any ideas?
Solution
The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell_i\in L$ we have at least one point that covers it. Let each interval $\ell_i$ be represented by $(c_i, h_i)$
The runs in $O(n\lg n)$ time.
We can show this is optimal. Let the solution obtained above be $S$ and let any feasible solution be $R$. We can show that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$.
If the above is not true then we have some $x_{i-1}\leq y_{j-1} < y_j < x_i$ for both $x\in R$ and both $y\in S$. In this case, the interval $\ell_k$ ending at $y_j$ would not be covered by $R$. $x_i$ can’t cover it, since by definition $y_j < x_i$. $x_{i-1}$ can’t cover it either. If it did, that would mean the start point of $\ell_k$ would be less than $x_{i-1}$ and thus also less than $y_{j-1}$. This can’t be the case, though, because then $y_{j-1}$ would have covered $\ell_k$, therefore removing it from the list of intervals in the next step our algorithm. Thus we have shown that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$ and therefore $S$ is optimal.
- Order all $\ell_i\in L$ by their $h_i$.
- While there are still items that need fridges.
- Buy a fridge and set it to $h_1$.
- For every item with $c_i\leq h_1$, put item $i$ in the fridge and discard the interval from $L$
The runs in $O(n\lg n)$ time.
We can show this is optimal. Let the solution obtained above be $S$ and let any feasible solution be $R$. We can show that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$.
If the above is not true then we have some $x_{i-1}\leq y_{j-1} < y_j < x_i$ for both $x\in R$ and both $y\in S$. In this case, the interval $\ell_k$ ending at $y_j$ would not be covered by $R$. $x_i$ can’t cover it, since by definition $y_j < x_i$. $x_{i-1}$ can’t cover it either. If it did, that would mean the start point of $\ell_k$ would be less than $x_{i-1}$ and thus also less than $y_{j-1}$. This can’t be the case, though, because then $y_{j-1}$ would have covered $\ell_k$, therefore removing it from the list of intervals in the next step our algorithm. Thus we have shown that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$ and therefore $S$ is optimal.
Context
StackExchange Computer Science Q#120734, answer score: 4
Revisions (0)
No revisions yet.