**[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 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 ≤ 10**

^{9}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