CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Maximum range of given any 'k' intervals[C++]

1. Junior Member Join Date
Nov 2017
Posts
3

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   Reply With Quote

2. Junior Member Join Date
Nov 2017
Posts
3

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  Reply With Quote

3. Member +   Join Date
Feb 2017
Posts
639

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.  Reply With Quote

4. Junior Member Join Date
Nov 2017
Posts
3

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)  Reply With Quote

5. Member +   Join Date
Feb 2017
Posts
639

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.  Reply With Quote

algorithm, c++  Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•