Maximum range of given any 'k' intervals.

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

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

#1 Vaxler  Icon User is offline

  • D.I.C Head

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

Posted Image

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;

    void read(int i)
    {
        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) {
        tabp[i].read(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  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13485
  • View blog
  • Posts: 53,844
  • Joined: 12-June 08

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

Posted 07 November 2017 - 10:49 AM

*
POPULAR

Also seen in these locations:

http://forums.codegu...y-k-intervals-C
https://stackoverflo...ny-k-intervalsc
https://codereview.s...any-k-intervals
https://linustechtip...ny-k-intervals/
Was This Post Helpful? 5
  • +
  • -

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

#4 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 - 02:33 PM

Any ideas?
Was This Post Helpful? 0
  • +
  • -

#5 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1376
  • View blog
  • Posts: 4,310
  • 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'

please read the arguments made by copeg on this java forum...

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

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

#7 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1376
  • View blog
  • Posts: 4,310
  • 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...

Posted Image


Or do you mean something else entirely ?
Was This Post Helpful? 1
  • +
  • -

#8 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 - 04:28 PM

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

Has length: 12 - 3 = 9
Was This Post Helpful? 0
  • +
  • -

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

#10 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

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

#11 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 - 05:01 PM

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

#12 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

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

#13 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 - 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 ;)
Was This Post Helpful? 0
  • +
  • -

#14 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 - 06:20 PM

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

#15 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1376
  • View blog
  • Posts: 4,310
  • 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

Posted Image

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.

When according to your own data the answer should be 2.

I will post a revised version shortly...
Was This Post Helpful? 1
  • +
  • -

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