118 lines
1.9 KiB
C++
118 lines
1.9 KiB
C++
[2, 9]
|
|
[3, 13]
|
|
[3, 10]
|
|
[3, 8]
|
|
[3, 6]
|
|
[3, 7]
|
|
[4, 8]
|
|
[4, 4] *
|
|
[4, 10]
|
|
[5, 11]
|
|
[7, 7] *
|
|
[7, 8]
|
|
[7, 12]
|
|
[7, 15]
|
|
[9, 12]
|
|
[9, 10] *
|
|
|
|
/*
|
|
|
|
Disjoint Intervals (https://www.interviewbit.com/problems/disjoint-intervals/)
|
|
|
|
Asked in:
|
|
Google
|
|
|
|
Problem Description
|
|
|
|
Given a set of N intervals denoted by 2D array A of size N x 2, the task is to find the length of maximal set of mutually disjoint intervals.
|
|
|
|
Two intervals [x, y] & [p, q] are said to be disjoint if they do not have any point in common.
|
|
|
|
Return a integer denoting the length of maximal set of mutually disjoint intervals.
|
|
|
|
|
|
|
|
Problem Constraints
|
|
|
|
1 <= N <= 105
|
|
|
|
1 <= A[i][0] <= A[i][1] <= 109
|
|
|
|
|
|
|
|
Input Format
|
|
|
|
First and only argument is a 2D array A of size N x 2 denoting the N intervals.
|
|
|
|
|
|
Output Format
|
|
|
|
Return a integer denoting the length of maximal set of mutually disjoint intervals.
|
|
|
|
|
|
Example Input
|
|
|
|
Input 1:
|
|
|
|
A = [
|
|
[1, 4]
|
|
[2, 3]
|
|
[4, 6]
|
|
[8, 9]
|
|
]
|
|
|
|
Input 2:
|
|
|
|
A = [
|
|
[1, 9]
|
|
[2, 3]
|
|
[5, 7]
|
|
]
|
|
|
|
|
|
|
|
Example Output
|
|
|
|
Output 1:
|
|
|
|
3
|
|
|
|
Output 2:
|
|
|
|
2
|
|
|
|
|
|
|
|
Example Explanation
|
|
|
|
Explanation 1:
|
|
|
|
Intervals: [ [1, 4], [2, 3], [4, 6], [8, 9] ]
|
|
Intervals [2, 3] and [1, 4] overlap.
|
|
We must include [2, 3] because if [1, 4] is included thenwe cannot include [4, 6].
|
|
We can include at max three disjoint intervals: [[2, 3], [4, 6], [8, 9]]
|
|
|
|
Explanation 2:
|
|
|
|
Intervals: [ [1, 9], [2, 3], [5, 7] ]
|
|
We can include at max two disjoint intervals: [[2, 3], [5, 7]]
|
|
*/
|
|
int Solution::solve(vector<vector<int> > &A) {
|
|
|
|
std::sort(A.begin(),A.end(),
|
|
[](const vector<int>& op1, const vector<int>& op2){
|
|
return (op1[0] < op2[0] );
|
|
});
|
|
|
|
int c = 1;
|
|
auto it = A.begin();
|
|
for (auto jt = A.begin()+1; jt != A.end(); ++jt){
|
|
if (it->at(1) < jt->at(0)){
|
|
c++;
|
|
it = jt;
|
|
} if (jt->at(1) < it->at(1)){
|
|
it = jt;
|
|
}
|
|
}
|
|
return c;
|
|
} |