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

Vaxler · November 7, 2017

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 ≤ 10⁹

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;

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