Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?

Question

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?

Answer 1

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)$

1. Order all $\ell_i\in L$ by their $h_i$.
2. While there are still items that need fridges.
   1. Buy a fridge and set it to $h_1$.
   2. 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.

Answer 2

I'd start with the shortest temperature range, stash everything that fits in it into a refrigerator, rinse and repeat. But a temperature range may overlap several that don't overlap among themselves, among those that do overlap search for a temperature that hits most ranges. This heuristic sounds like it should give a good solution, but I'd first look if there are is some counterexample (and I'd be thrilled to see a proof that it gives an optimum...).