CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    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

  2. #2
    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

  3. #3
    Join Date
    Feb 2017
    Posts
    677

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

    Quote Originally Posted by Vaxler View Post
    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.

  4. #4
    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)

  5. #5
    Join Date
    Feb 2017
    Posts
    677

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

    Quote Originally Posted by Vaxler View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured