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 61 ≤ k≤ n ≤ 10000001 ≤ a <b ≤ 109The 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;
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;
}
Thanks in advance
