# Maximum range of given any 'k' intervals.

• (6 Pages)
• 1
• 2
• 3
• Last »

## 75 Replies - 11567 Views - Last Post: 10 November 2017 - 11:58 AMRate Topic: 3 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=407452&amp;s=7d3c6cc54fe2795fae5900768a020a93&md5check=' + ipb.vars['secure_hash'], cur_rating: 2, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

# Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 10:44 AM

I have a problem with one task. The main content of this task is that we are given nn intervals [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.

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 are nn lines. Each one has 2 numbers, a and b, and they are representing the interval [a;b].

On the right side is the output. The first line contains the range of maximum intervals. The next line contains k indexes of intervals that have maximum common range.

The indexes are as follows:

[3;8] → index 1
[4;12] → index 2
[2;6] → index 3
...

1 ≤ k≤ n ≤ 1000000
1 ≤ a <b ≤ 109

The available memory is only 128 MB, so I can't implement interval tree for this task.

The code to optimized brute-force (I only print the maximum common range but have to print the indexes as well. Can anyone tell me how to implement a faster algorithm?
#include <iostream>
#include <algorithm>

using namespace std;

constexpr int MAX = 1000007;
int n, k_range, range_check;

struct rangeof
{
int p, k;
int nr;

{
cin >> p >> k;
nr = i;
}
};

rangeof tabp[MAX];

int maximum = 0;

bool sort_by_first(const rangeof & z1, const rangeof & z2)
{
if (z1.p < z2.p)
return true;
else if (z1.p == z2.p && z1.k > z2.k)
return true;

return false;
}

struct range {
int p, k;
};

bool visited[MAX];

int range(const rangeof & z)
{
return z.k - z.p;
}

bool reached_k = false;

void do_odd1(rangeof z1, int i, int k)
{
rangeof pom;

while (++i <= n && ++k <= k_range)
{
if (z1.k <= tabp[i].p)
return;

pom.p = max(z1.p, tabp[i].p);
pom.k = min(z1.k, tabp[i].k);

int dl = range(pom);

if (reached_k && dl <= maximum)
{
--k;
continue;
}

if (k == k_range) {
if (!reached_k)
reached_k = true;
if (dl > maximum)
maximum = dl;
--k;
continue;
}

do_odd1(pom, i, k);
--k;
}
}

void do_main()
{
for (int i = 1; i <= range_check; ++i)
{
if (!visited[i])
{
do_odd1(tabp[i], i, 1);
}
}
}

int main()
{
std::ios_base::sync_with_stdio(0);

cin >> n >> k_range;

range_check = n - k_range - 1;

for (int i = 1; i <= n; ++i) {
}

std::sort(tabp + 1, tabp + n + 1, sort_by_first);

do_main();

cout << maximum << endl;
}

This post has been edited by modi123_1: 07 November 2017 - 10:52 AM
Reason for edit:: Fixed URL

Is This A Good Question/Topic? 0

## Replies To: Maximum range of given any 'k' intervals.

### #2 modi123_1

• Suitor #2

Reputation: 15685
• Posts: 62,813
• Joined: 12-June 08

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 10:49 AM

POPULAR

### #3 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 10:53 AM

I don't know why the image isn't displayed so there's link to input and output.
The input and output fo the task.

@modi123_1
I know that it is seen in those locations. These are my threads.

### #4 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 02:33 PM

Any ideas?

### #5 snoopy11

• Engineering ● Software

Reputation: 1556
• Posts: 4,930
• Joined: 20-March 10

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 03:24 PM

Cross - posting on multiple forums is considered poor forum 'etiquette'

http://www.javaprogr...ss-posting.html

forum programmers give up their considerable knowledge and free time to answer your questions

and cross - posting can be considered by some, as wasting their time...

### #6 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 03:35 PM

I decided to post on multiple forums, beacause i couldn't get resposne to my question. I have limited time to do this task. I am looking at all threads and I won't leave it without answer when, for example, someone help me enough on other forum - i'll like it or I'll do some kind of things to increase this person's reputation and I'll of course appreciate it. Sorry for posting on multiple forums.

### #7 snoopy11

• Engineering ● Software

Reputation: 1556
• Posts: 4,930
• Joined: 20-March 10

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 04:22 PM

Range is such an ambiguous term it could mean a lot of things in statistics, arithmetic or mathematics...

do you mean by Range the Mid-Range as given by the equation...

Or do you mean something else entirely ?

### #8 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 04:28 PM

I meant the maximum length of inerval, for example:
Interval [a; b]:
[3; 12]

Has length: 12 - 3 = 9

### #9 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 04:53 PM

Other example:

Let's tell I have intervals as follows and number k = 3:

[1; 10] -> index 1
[2; 6] -> index 2
[3; 4] -> index 3
[4; 12] -> index 4

For optimal solution i would choose intervals about index: 1, 2 and 4. The maximum common length of these intervals is 2 -> The range of the maximum interval is [4; 6].
If I chose 1, 2, 3 the length would be 1. If I chose 1, 4, 3 it would be 1 as well.

### #10 snoopy11

• Engineering ● Software

Reputation: 1556
• Posts: 4,930
• Joined: 20-March 10

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 04:55 PM

Are you sure ?

As I refer you to your graphic in post #1 were it says

Quote

On the left side is an input - the first 2 numbers are respectively n - number of intervals, and k - number of any intervals

the numbers on the left are from the graphic 6 , 3

Quote

On the right side is the output. The first line contains the range of maximum intervals. The next line contains k indexes of intervals that have maximum common range.

The number on the first line is 4.

following your logic if it was the maximum length of interval ie 6-3 =3 not 4

If it was however the mid range of an int then 6+3/2 = 9/2 = 4 which would now give the correct answer...

It is highly important to get the right information or any help you receive on this will be useless.

### #11 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 05:01 PM

Vaxler, on 07 November 2017 - 04:53 PM, said:

Other example:

Let's tell I have intervals as follows and number k = 3:

[1; 10] -> index 1
[2; 6] -> index 2
[3; 4] -> index 3
[4; 12] -> index 4

For optimal solution i would choose intervals about index: 1, 2 and 4. The maximum common length of these intervals is 2 -> The range of the maximum interval is [4; 6].
If I chose 1, 2, 3 the length would be 1. If I chose 1, 4, 3 it would be 1 as well.

I gave an example. Sorry for bad English

### #12 snoopy11

• Engineering ● Software

Reputation: 1556
• Posts: 4,930
• Joined: 20-March 10

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 05:34 PM

You need clarification on this from your Lecturer as what you are saying makes no sense mathematically.

if k = 3 and k is the common interval.

and you have indexes as follows

[1; 10] -> index 1
[2; 6] -> index 2
[3; 4] -> index 3
[4; 12] -> index 4

if you choose index 1, 2 and 4 with k = 3

index 1 has the mid range 11/2 = 5;
index 2 has the mid range 8/2 = 4;
index 3 has the mid range 16/2 = 8;

so the range of the maximum interval is [4,8] not [4,6] as you state

if you go by the length of maximum interval.

index 1 has the length of maximum interval 10-1 =9
index 2 has the length of maximum interval 6-2 = 4
index 4 has the length of maximum interval 12-4 =8

so the range is now [4,9] again not [4.6]

You need to explain the problem better or point us to a website that explains the statistics and or mathematics you are using.

### #13 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 06:13 PM

That's not about counting mid-range. Ok - I'll try to present it better. I can't edit my first post so have to write it here.

6 3 n = 6, k = 3
// now n lines:
3 8 interval [3; 8]
4 12 ...
2 6
1 10
5 9
11 12

k is not the common interval. It is the number of intervals sharing common length.

Let's tell I have intervals as follows for n = 4, k = 3 (I'm setting them the indexes like in an array from 1 to 4 and sorting the intervals by the left number):

[1; 10] -> index 1
[2; 6] -> index 2
[3; 4] -> index 3
[4; 12] -> index 4

struct interval
{
int left, right;
}

Choosing intervals with indexes 1 and 2 will give us the common interval [2; 6]. The formula after sorting desribed above, for intervals [a1; b1] and [a2, b2] (a1 <= a2) is:

interval example = [max(a1.left, a2.left), min(a1.right, a2.right)];

So now i know that common interval of intervals with indexes 1 and 2 is [2; 6]. In next step i'm doing the same for common interval of interals with indexes 1 and 2, and interval [4; 12]. According to my formula
it'll give us common interval [4; 6] which length is 2.

The output to given example is:
2
1 2 4

Output:
2
1 4 2
is good as well(order doesn't matter).

And according to that formula i've written brute-force algorithm

### #14 Vaxler

Reputation: -5
• Posts: 51
• Joined: 07-November 17

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 06:20 PM

Vaxler, on 07 November 2017 - 06:13 PM, said:

k is not the common interval. It is the number of intervals sharing common length. />

EDIT:

k is not the common interval. It is the number of intervals sharing the maximum possible common interval.

### #15 snoopy11

• Engineering ● Software

Reputation: 1556
• Posts: 4,930
• Joined: 20-March 10

## Re: Maximum range of given any 'k' intervals.

Posted 07 November 2017 - 09:58 PM

I see,

Its an Arithmetic Interval...

Not a statistical Interval...

as found here...

https://en.wikipedia...rval_arithmetic

so you have the equation for that as

Anyway your program doesn't work as is...

if Input 4 and 3 for n and k respectively

then input

[1; 10]
[2; 6]
[3; 4]
[4; 12]

it gives the answer as 0.