Given $n$ closed intervals on a number line, the objective is to select exactly $m$ intervals such that they share at least one common coordinate point. The cost of a selection is defined as the difference between the maximum length and the minimum length among the chosen intervals. The length of an interval $[l, r]$ is calculated as $r - l$. The goal is to find the minimum possible cost. If no valid selection exists, the result should be indicated as impossible.

Algorithmic Approach

The solution combines sorting, coordinate compression, a segment tree, and the two-pointer technique.

1. Sorting by Length: Since the cost depends on the difference between the longest and shortest selected intervals, sorting all available intervals by their length allows us to control the cost window. By iterating through the sorted list, we can treat the current interval as the potential maximum length in a valid subset.
2. Coordinate Comprestion: The coordinates can be large, so direct indexign in a segment tree is inefficient. Collect all start and end points, sort them, and remove duplicates to map the original coordinates to a smaller range of indices.
3. Segment Tree: A segment tree is used to maintain the coverage count over the discretized coordinates. Each node stores the maximum coverage count in its range and supports lazy propagation for range updates. When an interval is added or removed, the corresponding range in the tree is updated.
4. Two-Pointer Technique: Maintain a window $[left, right]$ over the sorted intervals.
   • Expand the right pointer to include intervals, updating the segment tree.
   • Once the maximum coverage in the segment tree reaches $m$, a valid selection exists within the current window.
   • Calculate the cost using the lengths of the intervals at right and left.
   • Shrink the window from the left to find the minimal length difference while maintaining the validity condition, updating the segment tree accordingly.

Implementation Details

The following C++ implementation demonstrates this approach. It uses a structure to intervals, a vector for coordinate compression, and a class-based segment tree for encapsulation.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Interval {
    int l, r, length;
};

// Comparator to sort intervals by length
bool compareIntervals(const Interval& a, const Interval& b) {
    return a.length < b.length;
}

class SegmentTree {
private:
    struct Node {
        int max_val;
        int lazy_tag;
    };
    
    vector<Node> tree;
    int size;

    void push_up(int node) {
        tree[node].max_val = max(tree[node * 2].max_val, tree[node * 2 + 1].max_val);
    }

    void push_down(int node) {
        if (tree[node].lazy_tag != 0) {
            int left = node * 2;
            int right = node * 2 + 1;
            
            tree[left].lazy_tag += tree[node].lazy_tag;
            tree[left].max_val += tree[node].lazy_tag;
            
            tree[right].lazy_tag += tree[node].lazy_tag;
            tree[right].max_val += tree[node].lazy_tag;
            
            tree[node].lazy_tag = 0;
        }
    }

    void update(int node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            tree[node].max_val += val;
            tree[node].lazy_tag += val;
            return;
        }

        push_down(node);
        int mid = start + (end - start) / 2;
        if (l <= mid) update(node * 2, start, mid, l, r, val);
        if (r > mid) update(node * 2 + 1, mid + 1, end, l, r, val);
        push_up(node);
    }

public:
    SegmentTree(int n) {
        size = n;
        tree.resize(4 * n + 1, {0, 0});
    }

    void add_range(int l, int r, int val) {
        if (l > r) return;
        update(1, 1, size, l, r, val);
    }

    int get_max_coverage() {
        return tree[1].max_val;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Interval> intervals(n);
    vector<int> coordinates;
    coordinates.reserve(2 * n);

    for (int i = 0; i < n; ++i) {
        cin >> intervals[i].l >> intervals[i].r;
        intervals[i].length = intervals[i].r - intervals[i].l;
        coordinates.push_back(intervals[i].l);
        coordinates.push_back(intervals[i].r);
    }

    // Coordinate Compression
    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());
    
    int coord_count = coordinates.size();
    
    // Map original coordinates to compressed indices (1-based for Segment Tree)
    for (int i = 0; i < n; ++i) {
        intervals[i].l = lower_bound(coordinates.begin(), coordinates.end(), intervals[i].l) - coordinates.begin() + 1;
        intervals[i].r = lower_bound(coordinates.begin(), coordinates.end(), intervals[i].r) - coordinates.begin() + 1;
    }

    // Sort intervals based on length
    sort(intervals.begin(), intervals.end(), compareIntervals);

    SegmentTree seg_tree(coord_count);
    int min_cost = INT_MAX;
    int left = 0;

    for (int right = 0; right < n; ++right) {
        // Add current interval to the coverage map
        seg_tree.add_range(intervals[right].l, intervals[right].r, 1);

        // While the condition is met (at least one point covered by m intervals)
        while (seg_tree.get_max_coverage() >= m) {
            int current_cost = intervals[right].length - intervals[left].length;
            if (current_cost < min_cost) {
                min_cost = current_cost;
            }
            
            // Remove the leftmost interval to try and minimize length difference
            seg_tree.add_range(intervals[left].l, intervals[left].r, -1);
            left++;
        }
    }

    if (min_cost == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << min_cost << endl;
    }

    return 0;
}

Complexity Analysis

• Time Complexity: Sorting the intervals takes $O(N \log N)$. Coordinate compression also requires sorting, taking $O(N \log N)$. The two-pointer loop runs $N$ times, and each step involves segment tree operations which take $O(\log N)$. Thus, the total time complexity is $O(N \log N)$.
• Space Complexity: Storage for intervals, coordinates, and the segment tree requires $O(N)$ space.