Maximum range of given any 'k' intervals.

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

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

#31 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:42 AM

@r.stiltskin
Order doesn't matter.
@modi123_1
I have no any idea how to make it faster. I'll try the Skydiver option.

This post has been edited by Vaxler: 08 November 2017 - 10:44 AM

Was This Post Helpful? 0
  • +
  • -

#32 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:46 AM

You are three pages deep and with multiple folk helping you. At this point all I see is someone asking for them to do the work for you and bordering on being a help vampire .

Please _try_.
Was This Post Helpful? 0
  • +
  • -

#33 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:50 AM

View PostVaxler, on 08 November 2017 - 01:42 PM, said:

@r.stiltskin
Order doesn't matter.

That doesn't answer my question. My question has nothing to do with order.

You said

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


I'm asking:
would
Maximum length of interval = 2
Maximum Intervals occur at Indexes: 3 4 5 14 16
be correct?

How about
Maximum length of interval = 2
Maximum Intervals occur at Indexes: 5 8 9 14 16 ?

or
Maximum length of interval = 2
Maximum Intervals occur at Indexes: 1 4 5 9 16 ?

and so on...
Was This Post Helpful? 0
  • +
  • -

#34 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:53 AM

@r.stiltskin
Yes. All of them are the correct answers and order doesn't matter. Sorry for the confusion.

This post has been edited by Vaxler: 08 November 2017 - 10:57 AM

Was This Post Helpful? 0
  • +
  • -

#35 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3716
  • View blog
  • Posts: 13,476
  • Joined: 08-August 08

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

Posted 08 November 2017 - 03:02 PM

An example would be helpful. Show what an interval is, for example. Don't describe it. Show it.
What is a length of an interval? Again, don't describe it. Show it.
And for God's sake, don't list a bunch of numbers without labels! That's meaningless.
Show a, b, and k, then show what your intervals are, then show what your maximum interval(s) are, and why. Doing this will make things clearer for all. It might make it clear enough for you to complete the project on your own!
Was This Post Helpful? 0
  • +
  • -

#36 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 - 04:59 PM

@Skydiver

I have written the code to this pseudocode. I don't know how to make priority queue to store only 'k' items:

#include <iostream>
#include <queue>
using namespace std;

struct Interval
{
	Interval() {}
	int A, B;

	void read()
	{
		cin >> A >> B;
	}

	int get_key() {
		return B - A;
	}
};

struct IntervalInfo
{
	IntervalInfo() {}
	int      Index;
	Interval interval;
	int key;

	void read(int i)
	{
		interval.read();
		key = interval.get_key();
		Index = i + 1;
	}
};

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

	int n, k;

	cin >> n >> k;

	auto Func= [](IntervalInfo i1, IntervalInfo i2) {
		return i1.key < i2.key;
	};

	priority_queue<IntervalInfo, vector<IntervalInfo>, decltype(Func)> priorityQueue(Func);
	priority_queue<IntervalInfo, vector<IntervalInfo>, decltype(Func)> priorityQueue2(Func);

	for (int i = 0; i < n; i++)
	{
		IntervalInfo interval;

		interval.read(i);

		priorityQueue.push(interval);
	}

	int maxA = priorityQueue.top().interval.A;
	int minB = priorityQueue.top().interval.B;

	for (int i = 0; i < k; ++i)
	{
		auto interval = priorityQueue.top();
		priorityQueue.pop();
		priorityQueue2.push(interval);

		maxA = max(maxA, interval.interval.A);
		minB = min(minB, interval.interval.B)/>/>/>;
	}
	// Print out range of the overlap:
	cout << minB - maxA << endl;

	// Print out the indexes
	for (int i = 0; i < k; ++i)
	{
		auto inter = priorityQueue2.top();
		priorityQueue2.pop();
		cout << inter.Index << ' ';
	}
}


It doesn't work propely for many tests.
The output is:
1
1 14 2 5 15 7 3

Should be:
3
1 2 5 6 7 14 15 // can be different but the number above have to be 3

This post has been edited by Vaxler: 08 November 2017 - 05:00 PM

Was This Post Helpful? 0
  • +
  • -

#37 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 - 05:24 PM

@CTphpnwb

The input:

11   k
4    6
5    6
4    5
4    6
1    8
4    8
6    8
3    4
2    7
1    7
1    8


Images - there is given k = { 2, 3, 4, 5, 6 }:
https://imgur.com/a/rylb2

First image is the main input.
Second one is input of solution for k = 2.
Third one is input of solution for k = 3.
...

Segments of the interval colored green are the maximum common intervals for given 'k'.
Was This Post Helpful? 0
  • +
  • -

#38 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3716
  • View blog
  • Posts: 13,476
  • Joined: 08-August 08

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

Posted 08 November 2017 - 05:35 PM

That doesn't play well with your original post. What are a and b?
a = ?
b = ?

Are they 4,6 and then 5,6 and so on? What's 11?

The first step in finding a solution is properly defining the problem.
Was This Post Helpful? 0
  • +
  • -

#39 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 - 05:46 PM

If i only could edit that original post ...
n = 11 is the number of intervals.
In each next n lines there are a, b that are representing interval [a; b]. Everything else is seen on the pictures.
Was This Post Helpful? 0
  • +
  • -

#40 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 - 06:46 PM

View PostVaxler, on 08 November 2017 - 06:59 PM, said:

@Skydiver

I have written the code to this pseudocode. I don't know how to make priority queue to store only 'k' items:
Spoiler

It doesn't work propely for many tests.
The output is:
1
1 14 2 5 15 7 3

Should be:
3
1 2 5 6 7 14 15 // can be different but the number above have to be 3

What is the test data for that? Just telling me the expected result does help me reason out why it succeeded or failed. From what I can see from your other posts, your test data had a k=5, but for this particular test, k=7.

Also your implemention above doesn't really need two priority queues. Once you have the top k intervals with the longest ranges, you can simply put their indexes into a vector for later output.
Was This Post Helpful? 0
  • +
  • -

#41 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1852
  • View blog
  • Posts: 6,661
  • Joined: 19-February 09

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

Posted 08 November 2017 - 06:52 PM

What is the problem with the original (first) post, is it nn?

The data seems fairly clear:

The data format is
n k
a b
a b
a b
 etc.

Where 
n is the number of interval pairs
k is the number of intervals which will have a maximum common range
a and b are the interval pairs representing the interval [a;b].


Describing k is a bit difficult, later you say:

Quote

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

and

Quote

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


I can see from the first graphic that intervals 1, 2 and 4 contain the range whereas the other intervals don't.
Was This Post Helpful? 0
  • +
  • -

#42 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:23 PM

What is the definition of a "maximum common interval"?

If I have:
n=4 k=2
1 3
2 4
10 20
30 40

Is the correct answer:
1
1 2
Or:
0
3 4
?

If the former, is it because there must be at least k overlapping intervals even if the lengths of the intervals are much shorter than the other intervals?

If the latter, is it okay for there to be no overlap between the k longest intervals?
Was This Post Helpful? 0
  • +
  • -

#43 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3716
  • View blog
  • Posts: 13,476
  • Joined: 08-August 08

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

Posted 08 November 2017 - 07:43 PM

I'm not sure I understand the problem, but are you trying to do something like this?
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct interval {
	int a, b, range;
	interval(int x, int y): a(x), b(y) { range = abs(x - y); }

	void show() {
		cout << a << ", " << b << " range: " << range << endl;
	}
};
bool compare(interval &one, interval &other) { return one.range < other.range; }

int main()
{
	vector<interval> test;
	test.push_back(interval(4,6));
	test.push_back(interval(5,6));
	test.push_back(interval(4,5));
	test.push_back(interval(4,6));
	test.push_back(interval(1,8));
	test.push_back(interval(4,8));
	test.push_back(interval(6,8));
	test.push_back(interval(3,4));
	test.push_back(interval(2,7));
	test.push_back(interval(1,7));
	test.push_back(interval(1,8));

	for(size_t i = 0; i < test.size(); i++) {
		test[i].show();
	}
	cout << "\nSorted by range\n";
	sort(test.begin(), test.end(), compare);
	for(size_t i = 0; i < test.size(); i++) {
		test[i].show();
	}

	return 0;
}



My output:
4, 6 range: 2
5, 6 range: 1
4, 5 range: 1
4, 6 range: 2
1, 8 range: 7
4, 8 range: 4
6, 8 range: 2
3, 4 range: 1
2, 7 range: 5
1, 7 range: 6
1, 8 range: 7

Sorted by range
5, 6 range: 1
4, 5 range: 1
3, 4 range: 1
4, 6 range: 2
4, 6 range: 2
6, 8 range: 2
4, 8 range: 4
2, 7 range: 5
1, 7 range: 6
1, 8 range: 7
1, 8 range: 7


If that's right, then your largest range (interval??) is 7, it occurs twice, and its index is 1?
Was This Post Helpful? 0
  • +
  • -

#44 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • Joined: 20-March 10

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

Posted 09 November 2017 - 02:26 AM

Right eventually had time to

update this try out this one Im pretty sure will work

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

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

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

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

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

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

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

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

	return rv;
}


return_values enter_ab()
{

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

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

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

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

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

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

	}
	adder >> answerB;
	std::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;
	std::cout << "Enter values for [n and k]" << endl;

	values = enter_func();

	n = values.N;
	k = values.K;

	std::cout << "Enter values for [a and b]" << endl;
	for (int i = 0; i < n; i++)
	{
		std::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);

	common_index_array.erase(unique(common_index_array.begin(), common_index_array.end()), common_index_array.end());




	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j < n; j++)
		{

			if (index_array[j] == common_index_array[i]) { index_list.push_back(j); }
		}
	}




	std::cout << endl;
	std::cout << endl << "Maximum Intervals occur at Indexes: ";
	for (int j = 0; j < k - 1; j++)
	{
		if (index_list[j] != index_list[j + 1])
		{
			std::cout << index_list[j] + 1 << " ";
			list.push_back(index_list[j] + 1);
		}


	}

	std::cout << index_list[k - 1] + 1 << " ";
	list.push_back(index_list[k - 1] + 1);



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


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



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

	return 0;
}




You are lucky that these types of problems interest me...

And you have been very difficult to deal with you might want to change your attitude..
Was This Post Helpful? 0
  • +
  • -

#45 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 1378
  • View blog
  • Posts: 4,324
  • Joined: 20-March 10

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

Posted 09 November 2017 - 04:08 AM

Right cleaned up code last post on this matter

Ordering of Maximum intervals sorted ...

Other small logic changes...

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

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

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

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

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

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

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

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

	return rv;
}


return_values enter_ab()
{

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

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

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

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

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

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

	}
	adder >> answerB;
	std::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;
	std::cout << "Enter values for [n and k]" << endl;

	values = enter_func();

	n = values.N;
	k = values.K;

	std::cout << endl << "Enter values for [a and b]" << endl;
	for (int i = 0; i < n; i++)
	{
		std::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);

	common_index_array.erase(unique(common_index_array.begin(), common_index_array.end()), common_index_array.end());




	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j < n; j++)
		{

			if (index_array[j] == common_index_array[i]) { index_list.push_back(j); }
		}
	}




	std::cout << endl;
	std::cout << endl << "Maximum Intervals occur at Indexes: ";
	for (int j = 0; j < k - 1; j++)
	{
		if (index_list[j] != index_list[j + 1])
		{
			
			list.push_back(index_list[j] + 1);
		}


	}

	
	list.push_back(index_list[k - 1] + 1);
	list.erase(unique(list.begin(), list.end()), list.end());
	sort(list.begin(), list.end());
	

	for(int j = 0; j<k; j++)
	std::cout << list[j]  << " ";

	std::cout << endl;
	int max_array = 0, min_array = 999999;
	for (unsigned int i = 0; i < list.size(); i++)
	{
		max_array = max(max_array, data2[list[i] - 1].N);
		min_array = min(min_array, data2[list[i] - 1].K);
	}


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



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

	return 0;
}



Was This Post Helpful? 0
  • +
  • -

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