Maximum range of given any 'k' intervals.

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

75 Replies - 4521 Views - Last Post: 10 November 2017 - 11:58 AM Rate Topic: **--- 3 Votes

#16 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#17 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • 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()
{
	int number = 0, answerN = 0, answerK = 0;
	return_values rv;

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

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

	}
	adder >> answerN;
	cout << ", ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

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

	}
	adder >> answerK;
	cout << " ]";
	rv.N = answerN;
	rv.K = answerK;

	return rv;
}


return_values enter_ab()
{
	int number = 0, answerA = 0, answerB = 0;
	return_values rv;
	
	cout << "[ ";
	stringstream adder;
	while (number != 13)
	{
		
		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerA;
	cout << "; ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

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

	}
	adder >> answerB;
	cout << " ]";
	rv.N = answerA;
	rv.K = answerB;

	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

Was This Post Helpful? 1
  • +
  • -

#18 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • 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()
{
	
	int number = 0, answerN = 0, answerK = 0;
	return_values rv;

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

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);
			
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerN;
	cout << ", ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);
			
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerK;
	cout << " ]";
	rv.N = answerN;
	rv.K = answerK;

	return rv;
}


return_values enter_ab()
{
	
	int number = 0, answerA = 0, answerB = 0;
	return_values rv;
	
	cout << "[ ";
	stringstream adder;
	while (number != 13)
	{
		
		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);
			
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerA;
	cout << "; ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerB;
	cout << " ]";
	rv.N = answerA;
	rv.K = answerB;

	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 ??
Was This Post Helpful? 1
  • +
  • -

#19 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

#20 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#21 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • 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;
}

read n
read k
priorityQueue = new PriorityQueue<IntervalInfo>(maxItems: k, keyFunction<IntervalInfo> (interval) => interval.B - interval.A);
for (int i = 0; i < n; i++)
{
    read interval
    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
}


Was This Post Helpful? 1
  • +
  • -

#22 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

#23 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • 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...
Was This Post Helpful? 1
  • +
  • -

#24 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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


Your solution prints:
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 :)
Was This Post Helpful? 0
  • +
  • -

#25 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 20,142
  • Joined: 05-May 12

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

Posted 08 November 2017 - 09:28 AM

View PostVaxler, 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
Was This Post Helpful? 0
  • +
  • -

#26 Vaxler  Icon User is offline

  • D.I.C Head

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

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

Posted 08 November 2017 - 09:41 AM

View PostSkydiver, 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 ;)
Was This Post Helpful? 0
  • +
  • -

#27 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • 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()
{

	int number = 0, answerN = 0, answerK = 0;
	return_values rv;

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

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);

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

	}
	adder >> answerN;
	cout << ", ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);

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

	}
	adder >> answerK;
	cout << " ]";
	rv.N = answerN;
	rv.K = answerK;

	return rv;
}


return_values enter_ab()
{

	int number = 0, answerA = 0, answerB = 0;
	return_values rv;

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

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);

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

	}
	adder >> answerA;
	cout << "; ";
	adder.clear();
	number = 0;
	while (number != 13)
	{

		number = _getch();
		if (number == 8)
		{
			_putch(8);
			cout << " ";
			_putch(8);
			adder.seekp(-1, adder.cur);
			adder << ' ';
			adder.seekp(-1, adder.cur);
		}
		if (number >= 48 && number <= 57)
		{
			cout << number - 48;
			adder << (number - 48);
		}

	}
	adder >> answerB;
	cout << " ]";
	rv.N = answerA;
	rv.K = answerB;

	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...
Was This Post Helpful? 0
  • +
  • -

#28 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2014
  • View blog
  • Posts: 5,397
  • 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

Was This Post Helpful? 0
  • +
  • -

#29 Vaxler  Icon User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

#30 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 13495
  • View blog
  • Posts: 53,911
  • 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?
Was This Post Helpful? 0
  • +
  • -

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