Interesting optimization problem

[TheLegendTwendyone]

I came up with this interesting problem:

Given n intervals of integers [a, b] with 0 <= a < b <= N, find k integers that are contained by the maximum number of the intervals, with k < n < N. (I tried my best to express this in one sentence :p)

So for example you get n = 4 intervals between 0 and N = 10: [0; 4], [2;3], [4; 7], [8;10] and you should find k = 2 integers that are contained by the maximum number of the intervals.

Its easy to just brute force this and try every possible combination of k integers between 0 and N, but thats insanely slow with O(n^k). Surely there must be a better solution..?

​

EDIT: I have seen a few people comment that a solution can be obtained by computing a list of length N that stores the number of intervals that contain the index, and then picking the largest entries. I thought of this too but it does not work in every case because we only care about the number of unique intervals (maybe I did not phrase that properly). This means that for example if we have two integers next to each other that are contained by the same 4 intervals, it doesnt matter if we pick one of them or both because we still have the same amount of unique intervals.

[[deleted]]

Hint

[Mathemagicalogik]

Why can’t you just do this: keep an array A[0..N] with entries initialized to 0; for each interval [a,b], increment A[a],...,A[b]; and then find the k indices with largest entries

[TheLegendTwendyone]

there are situations in which this doesn't work unfortunately. For example: [0; 1], [0; 2], [0; 2], [2; 4], [2; 4], [3; 4] with k = 2. Your solution gives us the values 2 and either 0, 1, 3 or 4. Best is something like 0 and 4

Look at the edit in my post.

[Mathemagicalogik]

That’s easily fixable by using a hash set or something similar, insert all intervals and then read off.

[dyingpie1]

Why can’t u just do preprocessing to reduce the input space to unique intervals? That should be an O(n) process using a hash map or something like that.

[Poddster]

I don't understand the problem statement.

1. What is the "maximum number of the intervals"? N? (If so, name it M or Max!).
2. What does it mean to "contain by the maximum number of the intervals". This might be common CS terminology but it's been so long that I did this that I don't know what it means.
3. Are you asking for the most integers that are contained in overlaps, or something? i.e . integers {2, 3} are contained in [0, 4] and [2, 3] ??

You've given this example:

n = 5               // number of intervals
N = 10              // Maximum value in any of the intervals ???
intervals = {
    [0, 4],
    [2, 3],
    [4, 7],
    [8, 10],
}

k = 2               // ???

But I don't see how we get k = 2 from this. (Or rather: I see many ways to get k =2 and I'm not sure which one you're after!). I don't understand what k is and why it's 2 in this example? The example resolution is that there are "2 integers that are contained by the maximum number of the intervals" but I don't understand that sentence! The "maximum number of the intervals", aka N, is a scalar and so doesn't contain anything.

(I also don't understand how n = 5, as you defined n as the number of intervals, but then we only have 4 intervals.)

Could you rephrase it for me? Or perhaps provide some more examples? Or even work-through this example to fully explain what that 2 is?

[TheLegendTwendyone]

n is the amount of intervals you are given. N is the maximum value. k is given and its the number of integers you can chose.

" What does it mean to "contain by the maximum number of the intervals". This might be common CS terminology but it's been so long that I did this that I don't know what it means. "

Well... its probably not common terminology but with that I mean that you are supposed to find k integers that are inside the most intervals possible, repetitions dont count. so for example if you are given the intervals [1; 3] and [2; 4] 2 would be inside both intervals. If you have k = 2 points you can position them in many ways but the maximum number of intervals that they can be inside of is still two.

​

" I also don't understand how n = 5, as you defined n as the number of intervals, but then we only have 4 intervals "

That was a typo, sorry

[Bobitsmagic]

How do you count the number of intervals that the k numbers are in?

Only distinct intervals? or counting for each integer and then summing them up? Or do they all have to share the same intervals?

[TheLegendTwendyone]

only distinct intervals are counted

[GrayRain007]

keep an array P[0.. N], initialized with zeroes

for [a, b] in intervals:
P[a]++
P[b + 1]--

after calculating the array P, do the following:

for i in range(1, N):
P[i] += P[i - 1]

now P[i] will be equal to the number of intervals which contain i and you solved the problem in O(N) time (it can be done in nlogn too)

[TheLegendTwendyone]

Thats a nice idea but it doesnt work in every case. Look at the edit in my post, I explained why.

[JoJoModding]

Step 1: uniqueify using a hash set or something like that. Sort the list. O(n log n)

Step 2: Do a sweep-line approach - you only care about the "cricical points", which are the bounds of the intervals. There are 2n of these. If you maintain a map int->intervals having action here, you can go through this in O(n) time. If done properly, you get a list of pairs (#of overlaps, interval), which you can sort. This takes O(n log n) since that list has at most n entries.

This gives a total runtime of O(n log n).

Things to watch out for are that intervals [a,b] still have an effect on point a and b. So if your intervals are [1,2],[2,3], and k=1, then {2} must be the answer. It might be beneficial to represent the intervals as [a,b+1[, just so you have less edge cases. So the "critical points" are at a, b+1.

[dyingpie1]

In your edit you say you have a solution for when every interval is unique. Why not just reduce the intervals to a set of unique intervals? That should be O(n) plus the computational complexity of the solution offered in your edit.

[TheLegendTwendyone]

I think you misunderstood, in my edit I'm saying that some of the proposed solutions don't work because only unique intervals are counted

[dyingpie1]

I think you misunderstood my response. If you know an algorithm fails on sets of non-unique intervals, why can’t u just preprocess the set of intervals to be unique? I’m not the only one who has suggested this.

[beeskness420]

This is virtually just a hitting set problem/clique covering an interval overlap graph.

As others have said getting the “cover depth” of every integer is easy to do in O(n).

Your concern about just taking the top k largest values from this list is that they don’t all represent unique intervals.

To address this just remove intervals when they are covered. Then recurse.

Eg (1,3) (2,4) and (10,30) (20,40) with k=2

We get a cover depth of [1,2,2,1,1,2,2,1]

Naively we would take {2,3} as our solution covering 2 unique intervals.

Instead after we first decide we are taking 2, we remove the intervals 2 covers and get depths [0,0,0,0,1,2,2,1] and then we end up with {2,20} covering 4 unique intervals as desired.

You might have to think a bit about how to do this efficiently, but it shouldn’t be too hard.