Simple and Easy to Understand CPP Solution(O(nlogn))

programming
google
Tags: #<Tag:0x00007f1825ac98d0> #<Tag:0x00007f1825ac9790>

#1

//ans stores the final disjoint intervals
//compare function sort all intervals on the basis of end times in ascending order
//index is used to compare two intervals(index and i)

bool compare(const vector &A,const vector &B){
return A[1] < B[1];
}
int Solution::solve(vector<vector > &A) {
sort(A.begin(),A.end(),compare);
int ans = 1;
int index = 0;
int overlapping = 0;
for(int i=1;i<A.size();i++){
if(A[index][1] < A[i][0]){
ans++;
index = index + overlapping + 1;
overlapping = 0;
}else{
overlapping++;
}
}
return ans;
}