-
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...y-k-intervals/
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 n-set of intervals. Then generate all k-subsets of the n-set and select those whose members have a maximum overlapping interval of a specified size.
Since the number k-subsets of an n-set is n over k (a binominal coefficient) the real problem of course is the sheer size of the problem.
http://mathworld.wolfram.com/k-Subset.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 branch-and-bound solution:
The k-subsets are generated recursively. A new interval is added to a k-subset at each new recursive step down to a maximum depth of k. The overlap interval for a k-subset is updated when a new interval is added and if it turns out to be too small the k-subset is discarded (and with it the deeper recursive branch so that's the bound). The k-depth is only reached when the k-subset 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
|