# Maximum range of given any 'k' intervals.

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

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

### #16 Vaxler

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

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

Posted 07 November 2017 - 10:53 PM

Indeed it doesn't work as supposed to be working. Anyway I don't know how to write faster algorithm to this problem. Thanks anyway.

### #17 snoopy11

• Engineering ● Software

Reputation: 1437
• Posts: 4,626
• Joined: 20-March 10

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

Posted 08 November 2017 - 12:21 AM

Right,

I have got it to this...

```#include <iostream>
#include <algorithm>
#include <cmath>
#include <conio.h>
#include <sstream>
#include <vector>
using namespace std;

struct return_values
{
int N;
int K;
};

return_values enter_func()
{
return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << ", ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}

return_values enter_ab()
{
return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << "; ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}
int main()
{
int n = 0, k = 0, interval = 0;
return_values values, common_interval;
vector<return_values> data;
cout << "Enter values for [n and k]" << endl;

values = enter_func();
n = values.N;
k = values.K;
for (int i = 0; i < n; i++)
{
cout << endl << "Index " << i + 1 << " ";
data.push_back(enter_ab());
}

int Max, Min, MaxArray, MinArray;
Max = ((int)max(data[0].N, data[1].N));
Min = ((int)min(data[0].K, data[1].K));// choose first two indexes

MaxArray = max(Max, data[3].N);
MinArray = min(Min, data[3].K);  // choose last index

cout << endl << "Output: Common Interval [" << MaxArray << ", " << MinArray << " ]" << endl;
interval = abs(MaxArray - MinArray);
cout << "Length of Interval " << interval << endl;
cin.ignore();
cin.get();

return 0;
}

```

which works for the special case n = 4 , k =3

But I don't understand the rules for choosing k indexes as you never explained it in enough detail.

I now need the general rule for choosing indexes so I can implement a more general program.

Thanks.

This post has been edited by snoopy11: 08 November 2017 - 01:05 AM
Reason for edit:: updated code

### #18 snoopy11

• Engineering ● Software

Reputation: 1437
• Posts: 4,626
• Joined: 20-March 10

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

Posted 08 November 2017 - 06:18 AM

I have the full solution.

```#include <iostream>
#include <algorithm>
#include <cmath>
#include <conio.h>
#include <sstream>
#include <vector>
using namespace std;

struct return_values
{
int N;
int K;
};

bool wayToSort(return_values i, return_values j) { return i.N < j.N; }
bool array_sort(int i, int j) { return i > j; }

return_values enter_func()
{

return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << ", ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}

return_values enter_ab()
{

return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << "; ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}
int main()
{
int n = 0, k = 0, interval = 0;
return_values values;
vector<return_values> data, data2;
vector<int> common_index_array;
vector<int> index_array, index_list;
cout << "Enter values for [n and k]" << endl;

values = enter_func();

n = values.N;
k = values.K;
for (int i = 0; i < n; i++)
{
cout << endl << "Index " << i + 1 << " ";
data.push_back(enter_ab());
}

for (unsigned int i = 0; i < data.size(); i++)
data2.push_back(data[i]);

sort(data.begin(), data.end(), wayToSort);

// find top k intervals of maximum length
vector<int> MaxArray, MinArray;
for (int j = 0; j < n; j++)
{
common_index_array.push_back(abs(data2[j].N - data2[j].K));
index_array.push_back(abs(data2[j].N - data2[j].K));
}

sort(common_index_array.begin(), common_index_array.end(),array_sort);// sort array
for (int j = 0; j < k; j++)
{
for(int i =0; i <n; i++)
if (index_array[i] == common_index_array[j]) { index_list.push_back(i); }
}

for (int i = 0; i < k - 1; i++)
{
MaxArray.push_back(max(data[index_list[i]].N, data[index_list[i + 1]].N));
MinArray.push_back(min(data[index_list[i]].K, data[index_list[i + 1]].K));
}

int max_array, min_array;
max_array = MaxArray[k-2];
min_array = MinArray[k-2];
cout << endl << "Output: Common Interval [" << max_array << ", " << min_array << " ]" << endl;
interval = abs(max_array - min_array);
cout << "Length of Interval " << interval << endl;

sort(index_list.begin(), index_list.end());
cout << "Maximum Intervals occur at Indexes: ";
for (unsigned int j = 0; j < index_list.size(); j++)
{
cout << index_list[j]+1 << " ";
}

cin.ignore();
cin.get();

return 0;
}

```

You are very lucky...
Tricky problem who set it for you ??

### #19 Vaxler

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

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

Posted 08 November 2017 - 07:34 AM

Thank you very much! I've liked you every single post. The Profesor of University set it to me.

1) Unfortunately there are tests that this soultion print wrong answers. I reviewed it.
The chosen interval's indexes are good, but there are few duplicates in output. There's problem with counting the maximum length of the interval as well.

For the test:
Input:
18 3
5 8
1 6
1 7
2 3
2 6
6 8
4 7
1 7
3 5
2 3
5 7
3 6
7 8
2 4
1 6
2 8
3 7
2 4

Output is:
1
3 3 3 8 8 8 16 16 16

Should be:
5
3 8 16

The chosen intervals, by this solution are the good ones. Only counting maximum length is bad one:
[1; 7], [1; 7] and [2; 8]

2) Something went wrong and there is and error in Visual Studio: vector subscript is out of range. Program crashes. There's problem with line(debugged it):
```max_array = MaxArray[k - 2];
```

I think the problem is also with line:
```min_array = MinArray[k - 2];
```

This is the test while program is crashing:
5 1
1 7
3 4
2 3
2 3
6 8

Could you repair it? Thank you very much again. Really thank you for your time. Regards

### #20 Vaxler

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

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

Posted 08 November 2017 - 07:50 AM

This code is very time-consuming. It's a far way better than exponential complexity(my brute-force algorithm), but for big data it won't work:

```	for (int j = 0; j < k; j++)
{
for (int i = 0; i <n; i++)
if (index_array[i] == common_index_array[j]) { index_list.push_back(i); }
}
```

So for n = 1000000 and k = 1000000, time complexity is O(n2) what gives so much operations: 1012.

Thank you for your time. Regards.

### #21 Skydiver

• Code herder

Reputation: 6011
• Posts: 20,683
• Joined: 05-May 12

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

Posted 08 November 2017 - 07:54 AM

Maybe I'm just being naive, or I'm not looking a things through the point of view of the computer science glasses, but this looks to be a pretty simple problem. Here's pseudo code of how I would tackle the problem.
```struct Interval
{
int A, B;
}

struct IntervalInfo
{
int      Index;
Interval Interval;
}

priorityQueue = new PriorityQueue<IntervalInfo>(maxItems: k, keyFunction<IntervalInfo> (interval) => interval.B - interval.A);
for (int i = 0; i < n; i++)
{
priorityQueue.Enqueue(new IntervalInfo{ Index = i + 1, Interval = interval});
}

maxA = priorityQueue[0].A;
minB = priorityQueue[0].B;
foreach(intervalInfo : priorityQueue)
{
maxA = max(maxA, intervalInfo,A);
minB = min(minB, intervalInfo.B)/>/>;
}

// Print out range of the overlap:
write max(0, minB - maxA)

// Print out the indexes
foreach(intervalInfo : priorityQueue)
{
write intervalInfo.Index
}

```

### #22 Vaxler

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

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

Posted 08 November 2017 - 08:18 AM

Thanks for reply. I don't understand this pseudocode:
```priorityQueue = new PriorityQueue<IntervalInfo>(maxItems: k, keyFunction<IntervalInfo> (interval) => interval.B - interval.A);
```

Could you explain it? Thanks

### #23 snoopy11

• Engineering ● Software

Reputation: 1437
• Posts: 4,626
• Joined: 20-March 10

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

Posted 08 November 2017 - 08:23 AM

Oh well back to the drawing board !

Try try again...

### #24 Vaxler

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

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

Posted 08 November 2017 - 09:13 AM

Hello again,

For test:
16 5
2 5
6 7
2 7
1 5
3 8
5 7
2 3
3 5
3 5
3 4
6 7
4 6
2 4
3 5
4 7
1 7

Maximum length of interval = 1
Maximum Intervals occur at Indexes: 1 3 3 4 5 5 15 16

Interval with index 15 [4; 7] should not be taken into account. If we do, it'll be wrong answer. On the other hand it would be incorrect to the main content of the task: k = 5 and we are printing six indexes(I don't take into account the duplicates of indexes).
So problem is with printing indexes as well.

It should be:
Maximum length of interval = 2
Maximum Intervals occur at Indexes: 1 3 4 5 16

Thanks for your time again. Regards

### #25 Skydiver

• Code herder

Reputation: 6011
• Posts: 20,683
• Joined: 05-May 12

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

Posted 08 November 2017 - 09:28 AM

Vaxler, on 08 November 2017 - 10:18 AM, said:

Thanks for reply. I don't understand this pseudocode:
```priorityQueue = new PriorityQueue<IntervalInfo>(maxItems: k, keyFunction<IntervalInfo> (interval) => interval.B - interval.A);
```

Could you explain it? Thanks />

Create a priority queue that can only hold k items maximum, and where the key used for priorities is the result of Interval.B - Interval.A

### #26 Vaxler

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

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

Posted 08 November 2017 - 09:41 AM

Skydiver, on 08 November 2017 - 09:28 AM, said:

Create a priority queue that can only hold k items maximum, and where the key used for priorities is the result of Interval.B - Interval.A

At the top of priority queue(Heap) shuold be lower or higher values? Regards

### #27 snoopy11

• Engineering ● Software

Reputation: 1437
• Posts: 4,626
• Joined: 20-March 10

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

Posted 08 November 2017 - 10:13 AM

Well,

I fixed the codes glaring logic errors, however wasnt too far away

here is the code

```#include <iostream>
#include <algorithm>
#include <cmath>
#include <conio.h>
#include <sstream>
#include <vector>
using namespace std;

struct return_values
{
int N;
int K;
};

bool wayToSort(return_values i, return_values j) { return i.N < j.N; }
bool array_sort(int i, int j) { return i > j; }

return_values enter_func()
{

return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << ", ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}

return_values enter_ab()
{

return_values rv;

cout << "[ ";
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);

}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << "; ";
number = 0;
while (number != 13)
{

number = _getch();
if (number == 8)
{
_putch(8);
cout << " ";
_putch(8);
}
if (number >= 48 && number <= 57)
{
cout << number - 48;
}

}
cout << " ]";

return rv;
}
int main()
{
int n = 0, k = 0, interval = 0;
return_values values;
vector<return_values> data, data2;
vector<int> common_index_array;
vector<int> index_array, index_list, list;
cout << "Enter values for [n and k]" << endl;

values = enter_func();

n = values.N;
k = values.K;
for (int i = 0; i < n; i++)
{
cout << endl << "Index " << i + 1 << " ";
data.push_back(enter_ab());
}

for (unsigned int i = 0; i < data.size(); i++)
data2.push_back(data[i]);

sort(data.begin(), data.end(), wayToSort);

// find top k intervals of maximum length
vector<int> MaxArray, MinArray;
for (int j = 0; j < n; j++)
{
common_index_array.push_back(abs(data[j].N - data[j].K));
index_array.push_back(abs(data2[j].N - data2[j].K));
}

sort(common_index_array.begin(), common_index_array.end(), array_sort);// sort array
for (int j = 0; j < n; j++)
{
for (int i = 0; i < k; i++)
if (index_array[j] == common_index_array[i]) { index_list.push_back(j); }
}

sort(index_list.begin(), index_list.end());
cout << endl << "Maximum Intervals occur at Indexes: ";
for (unsigned int j = 0; j < index_list.size(); j++)
{
if (j < index_list.size() - 1)
{
if (index_list[j] != index_list[j + 1])
{
cout << index_list[j] + 1 << " ";
list.push_back(index_list[j] + 1);
}
}
}
cout << index_list[index_list.size() - 1] + 1 << " ";
list.push_back(index_list[index_list.size() - 1] + 1);

int max_array = 0, min_array = 999999;
for (int i = 0; i < k; i++)
{
max_array = max(max_array, data2[list[i] - 1].N);
min_array = min(min_array, data2[list[i] - 1].K);
}

cout << endl << "Output: Common Interval [" << max_array << ", " << min_array << " ]" << endl;
interval = abs(max_array - min_array);
cout << "Length of Interval " << interval << endl;

cin.ignore();
cin.get();

return 0;
}

```

You may wish however to take Skydiver's advice its probably a simpler route as I tend to overthink things a little bit....

also the code needs refactored and cleaned up a bit been busy with other things today... so not had a lot of time...

### #28 r.stiltskin

• D.I.C Lover

Reputation: 2030
• Posts: 5,429
• Joined: 27-December 05

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

Posted 08 November 2017 - 10:37 AM

I still find your explanation of the problem to be ambiguous. Looking at your example in Post 24:

Quote

For test:
16 5
2 5
6 7
2 7
1 5
3 8
5 7
2 3
3 5
3 5
3 4
6 7
4 6
2 4
3 5
4 7
1 7

...

It should be:
Maximum length of interval = 2
Maximum Intervals occur at Indexes: 1 3 4 5 16

The intervals at indexes: 1 3 4 5 8 9 14 16 all overlap on the interval 3,5 (length 2), so would any size 5 subset of {1, 3, 4, 5, 8 , 9, 14, 16} be a correct solution?
e.g.:
1 3 4 5 8
or 1 3 4 5 9
or 1 3 4 5 14
etc...

edit: sorry, wrong post number

This post has been edited by r.stiltskin: 08 November 2017 - 10:39 AM

### #29 Vaxler

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

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

Posted 08 November 2017 - 10:39 AM

Ok. I really thank you anyway. If you have a time, then just update the code please. Test:
16 5
2 5
6 7
2 7
1 5
3 8
5 7
2 3
3 5
3 5
3 4
6 7
4 6
2 4
3 5
4 7
1 7

prints the wrong answer again. Regards

### #30 modi123_1

• Suitor #2

Reputation: 13768
• Posts: 54,954
• Joined: 12-June 08

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

Posted 08 November 2017 - 10:42 AM

Why don't *YOU* update the your code?