Search In
• More options...
Find results that contain...
Find results in...

# Task: Maximum Range Of Given Any "k" Intervals.

I have a problem with one task. The main content of this task is that we are given n 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 n 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 maximum common range of any k  intervals. The next line contains k indexes of intervals that have maximum common range.

The indexes of the intervals are as follows:

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

[1; 10] → index 4

[5; 9] → index 5

[11; 12] → index 6

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

The available memory is only 128 MB, so I suppose that I can't implement interval tree for this task, but maybe i'm wrong.

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>
#include <queue>

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;
}```

Any ideas?

?