Maximum range of given any 'k' intervals[C++]
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

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

  1. #1
    Join Date
    Nov 2017
    Posts
    2

    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
    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

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)