Algorithm for downsampling array of intervals

Update 1:

Below is my original post which I initially deleted, because there were issues with displaying the equations and also I wasn't very confident if it really makes sense. But later, I figured that the optimisation problem that I described can be actually solved efficiently with DP (Dynamic programming).

So I did a sample C++ implementation. Here are some results:

Here is a live demo that you can play with in your browser (make sure browser support WebGL2, like Chrome or Firefox). It takes a bit to load the page.

Here is the C++ implementation: link

---

Update 2:

Turns out the proposed solution has the following nice property - we can easily control the importance of the two parts F₁ and F₂ of the cost function. Simply change the cost function to F(α)=F₁ + αF₂, where α >= 1.0 is a free parameter. The DP algorithm remains the same.

Here are some result for different α values using the same number of intervals N:

Live demo ^{(WebGL2 required)}

As can be seen, higher α means it is more important to cover the original input intervals even if this means covering more of the background in-between.

---

Original post

Even-though some good algorithms have already been proposed, I would like to propose a slightly unusual approach - interpreting the task as an optimisation problem. Although, I don't know how to efficiently solve the optimisation problem (or even if it can be solved in reasonable time at all), it might be useful to someone purely as a concept.

---

First, without loss of generality, lets declare the blue color to be background. We will be painting N green intervals on top of it (N is the number provided to the downsample() function in OP's description). The i^th interval is defined by its starting coordinate 0 <= x_i < x_max and width w_i >= 0 (x_max is the maximum coordinate from the input).

Lets also define the array G(x) to be the number of green cells in the interval [0, x) in the input data. This array can easily be pre-calculated. We will use it to quickly calculate the number of green cells in arbitrary interval [x, y) - namely: G(y) - G(x).

We can now introduce the first part of the cost function for our optimisation problem:

The smaller F₁ is, the better our generated intervals cover the input intervals, so we will be searching for x_i, w_i that minimise it. Ideally we want F₁=0 which would mean that the intervals do not cover any of the background (which of course is not possible because N is less than the input intervals).

However, this function is not enough to describe the problem, because obviously we can minimise it by taking empty intervals: F₁(x, 0)=0. Instead, we want to cover as much as possible from the input intervals. Lets introduce the second part of the cost function which corresponds to this requirement:

The smaller F₂ is, the more input intervals are covered. Ideally we want F₂=0 which would mean that we covered all of the input rectangles. However, minimising F₂ competes with minimising F₁.

Finally, we can state our optimisation problem: find x_i, w_i that minimize F=F₁ + F₂

---

How to solve this problem? Not sure. Maybe use some metaheuristic approach for global optimisation such as Simulated annealing or Differential evolution. These are typically easy to implement, especially for this simple cost function.

Best case would be to exist some kind of DP algorithm for solving it efficiently, but unlikely.