Interval Minimum Coverage (IMPORTANT)

https://www.lintcode.com/problem/1668/description?_from=cat

There are n intervals in number axis. Now we need to choose some points to make that there is at least one point in each interval.

Return the minimum number of chosen points.

1 <= n <= 10^4

Example 1:
Input: [(1,5), (4,8), (10,12)]
Output: 2
Explanation:
  Choose two points: 5, 10
  The first  interval [1, 5] contains 5
  The second interval [4, 8] contains 5
  The third  interval [10, 12] contains 10

Example 2:
Input: [(1,5), (4,8), (5,12)]
Output: 1
Explanation: All intervals contain 5


/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

---------------------------------------------------------------------------------------------------------------------------------------
CODE #1

class Solution {
public:
    static bool cmp(Interval &p, Interval &q){
        if(p.end!=q.end){
            return p.end<q.end;
        }
        return p.start>q.start;
    }

    int getAns(vector<Interval> &a) {
        sort(a.begin(),a.end(),cmp);
        int res=1;
        int endPrev=a[0].end;
        for(int i=1;i<a.size();i++){
            if(a[i].start>endPrev){
                endPrev=a[i].end;
                res++;
            }
        }
        return res;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------
CODE #2

class Solution {
public:
    int getAns(vector<Interval> &a) {
        sort(a.begin(),a.end());
        int res=1;
        int eP=a[0].end;  //end previous point
        for(int i=1;i<a.size();i++){
            if(eP<a[i].start){
                res++;
                eP=a[i].end;
            }
            else{
                eP=min(eP,a[i].end);  // you wanna maintain the minimum eP so that prev guys have points within them
            }
        }
        return res;
    }
};