Algorithm {Maximum matching of selected points in the interval}

Algorithm {Maximum matching of selected points in the interval}

Maximum matching of selected points in the interval

Definition

Given an interval set A (each interval [l,r] is an integer), you need to select a point set P from the real number domain so that there is a subset SA of A, satisfying: There is a double Shoot P<->SA so that point x in P is included in the area [l,r] of SA (i.e. l<=x<=r);
Find the maximum size of the point set P; (In short, make the point set P as large as possible so that every point in P can match the interval in A one-to-one)
. For example, A: {[1,1], [2,2], [1,2]}, then the answer is 2, select P= {1,2}, SA={[1,1] [2,2]} (SA is not unique);

Algorithm

{ Mistake

Sort A by the left endpoint and maintain a global variable pos. If l,r >= 0 then let pos=-1 (indicates that it has been selected The P sets are all points of <=pos), for the current interval [l,r], if r >= max(pos + 1,l) Then select max(pos + 1,l) This point matches the current interval;

long long L = -1;
int ANS = 0;
for( auto & amp; i : A){
    auto lef = i.first, rig = i.second;
    if(rig >= max(L + 1, lef)){
        L = max(L + 1,lef); //Select L to match the current interval `i`;
         + + ANS;
        break;
    }
}

This greedy strategy is actually wrong...
For example, [1,1], [1,3], [2,2], your answer is 2, but the actual answer is 3;

}

The correct approach is also to be greedy, but not as simple as the greed above...
If 0<=l/r<=1e18, traverse for( pos : [0,1,...,1e18]):
. 1: [Delete all right endpoint intervals in A];
. 2: [Select an interval with the smallest right endpoint among all the left endpoint <=pos intervals in A T];
. (T must contain pos at this time) Then pos-T is a match. Of course, T is deleted from A;
Although it is also greedy, it is much more complicated than the above method;
There is no proof here, after all, the greedy question...; A simple proof, at this time [0,...pos-1] does not matter that they have already matched, so 1: is Reasonable, for the T selected by 2:, for example, it is [l,r], and its [l,pos] subinterval Don't worry about it because it is on the left side of pos. The key is to look at the sub-range of [pos + 1, r] because r satisfies (covers pos), which means that the [pos + 1, r]< of the interval T among all current intervals that satisfy (covering pos) /code>The sub-interval is the smallest, which means that it leaves more space and possibility for the next point [pos + 1, pos + 2,...] because In the remaining intervals, the R>r in their [pos + 1, R] are very large, which means the selectivity is large, that is, the selected T is the worst, and the rest of the intervals are excellent;

{
    __A: Collection of intervals;
    __N: __A’s length;
    Sort `__A` by *left endpoint*;
    int64_t __pos = 0; // coordinates of point
    priority_queue< pair<int64_t,int64_t>, vector<pair<int64_t,int64_t>>, greater<>> __heap; // Its elements are `[right endpoint, left endpoint]`;
    for(int __ind = 0;;){
        //>< `A[ind].first(left endpoint) > pos`;
        while( __heap.empty()==false & amp; & amp; __heap.top().first<__pos){ // The *right endpoint* of the range of the top element of the heap is `heap.top().first`;
            __heap.pop();
        }
        if( false == __heap.empty()){
            //><The point `pos` matches the interval corresponding to `Q.top()`;
            __heap.pop();
        }

        if(__heap.empty()){
            if( __ind == __N){ break;}
            __pos = A[__ind].first;
        }
        else{
             + + __pos;
        }
        while( __ind<__N & amp; & amp; A[__ind].first<=__pos){
            __heap.push( {A[__ind].second, A[__ind].first}); + + __ind;
        }
    }
}