
November 6th, 2017, 01:36 PM
#1
Maximum range of given any 'k' intervals[C++]
I have a problem with one task.
The main content of this task is that we are given n invervals [a; b] and number k. We have to find the maximum common range of any k intervals and print the indexes of intervals, that have maximum common range, to output.
https://i.stack.imgur.com/6aRxz.png
On the left side is an input  the first 2 numbers are respectively n  number of intervals, and k  number of any intervals having a maximum common range. The next n lines have 2 numbers a and b and they are representing the interval [a; b].
On the right side is and output. The first line contains the range of maximum interval. The next line contain k indexes of intervals that have maximum common range. The indexes are as follows:
3 8 > index 1
4 12 > index 2
2 6 > ...
...
1 ≤ k ≤ n ≤ 1000000
1 ≤ a < b ≤ 10^9
The avaible memory is only 128 MB, so I can't implement interval tree for this task.
The problem is I have no idea how to implement a fast algorithm. Is anyone able to write a fast algorithm for this task?
Sorry for bad English

November 6th, 2017, 02:00 PM
#2
Re: Maximum range of given any 'k' intervals[C++]
And the code i've written. Can aynone tell me how to make it faster? Faster implementation?
Here i didn't print the indexes of intervals but it has to do it:
https://ideone.com/sYCVeL

November 27th, 2017, 06:02 AM
#3
Re: Maximum range of given any 'k' intervals[C++]
Originally Posted by Vaxler
maximum common range
Here's a somewhat more elaborate description of the problem with a figure illustrating the meaning of "maximum common range",
https://linustechtips.com/main/topic...ykintervals/
I interpret this figure to show that the intervals 1, 2 and 4 (that is [3,8], [4,12] and [1,10]) all overlap a common interval (range) with the specified size of 4 (corresponding to interval [4,8]).
Now lets say the specified overlap size were 3, would then interval [4,7] do? I guess not because although [4,7] is a common interval it's not a maximum common interval since there's a larger one namely [4,8].
So the problem is simple in principle. Say we have an nset of intervals. Then generate all ksubsets of the nset and select those whose members have a maximum overlapping interval of a specified size.
Since the number ksubsets of an nset is n over k (a binominal coefficient) the real problem of course is the sheer size of the problem.
http://mathworld.wolfram.com/kSubset.html
Last edited by wolle; November 27th, 2017 at 08:17 AM.

November 27th, 2017, 08:17 AM
#4
Re: Maximum range of given any 'k' intervals[C++]
The problem is just solved. I've done it on my own. Key here was a priority queue having maximum k elements and binary search by ranks of intervals.
Complexity O(n*logn)

November 27th, 2017, 08:47 AM
#5
Re: Maximum range of given any 'k' intervals[C++]
Originally Posted by Vaxler
The problem is just solved.
Well, congratulations!
I was about to suggest a branchandbound solution:
The ksubsets are generated recursively. A new interval is added to a ksubset at each new recursive step down to a maximum depth of k. The overlap interval for a ksubset is updated when a new interval is added and if it turns out to be too small the ksubset is discarded (and with it the deeper recursive branch so that's the bound). The kdepth is only reached when the ksubset has a valid overlap interval.
Last edited by wolle; November 27th, 2017 at 08:51 AM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
