Problem Statement

You are given a list of intervals intervals, where each interval is a pair of integers [start, end]. A pair [starti, endi] is said to cover another pair [startj, endj] if starti <= startj and endi >= endj. In other words, interval i covers interval j if every point in j is also in i.

The task is to remove all intervals that are covered by another interval in the list, and return the number of remaining intervals.

Examples

Example 1:

Input: intervals = [[1, 4], [3, 6], [2, 8]]
Output: 2

Explanation:
- Interval [3, 6] is covered by [2, 8], so it is removed.
- Intervals [1, 4] and [2, 8] remain, so the output is 2.

Example 2:

Input: intervals = [[1, 4], [2, 3]]
Output: 1

Explanation:
- Interval [2, 3] is covered by [1, 4], so it is removed.
- Only interval [1, 4] remains, so the output is 1.

Different Approaches

1️⃣ 

Intuition:

1.The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.
	eg Interval [3,6] is covered by [2,8], therefore it should be removed.
	
	Let see the Number line :)
	
	                                           1  2  3  4  5  6  7  8
											   1-------4
											         3--------6
												  2-----------------8
	clearly we can see that [3 6] is covered by [2,8] and therefore it should be removed.

2. We will Sort the vector in ascending order to get this type of arrangement.
		//e.g. (1,5), (1,8), (2,9), (3,5), (4,7), (4,9)
		
3. For finding the remaining interaval, ifa[1][0] && a[1][1] both greater than a[0][0] && a[0][1],
this means the previous interval is not covered by the next one, therefore we will increase the count.
			consider the case [[1,3],[2,4],[4,8]]
								1   2  3  4  5  6  7  8
								1------3
									2-----4
									      4-----------8
											 
			No interval is completely overlaped by other therefore remainig interaval are 3.
			
			how answer is 3 , at first cnt is initialised to 1
			now a[0,0] i.e 1 and a[1,0] i.e 2   1 < 2 also,
			    a[0,1] i.e 3 and a[1,1] i.e 4   3 < 4    , therefore cnt is incremented by 2 now,
					
					also a[2,0] and a[2,1] satisy same condition with a[1,0] and a[1,1] , cnt becomes 3

Code:

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        
        // sorting the intervals(vector)
        sort(intervals.begin(),intervals.end());        
           
        int x1 = intervals[0][0];
        int x2 = intervals[0][1];
        
		 int res = 1;  //one for x1 and x2;
		
		// ifa[i][0] && a[i][1] both greater than a[i-1][0] && a[i-1][1]
		// increase the cnt.
        for(int i= 1; i<intervals.size(); ++i)
        {
            if(intervals[i][0] > x1 && intervals[i][1] > x2)
                ++res;
            
			// updating x1 & x2 with next intervals
			// as we are comparing from upcoming ones.
            if(intervals[i][1] > x2)
            {
                x1 = intervals[i][0];
                x2 = intervals [i][1];
            }
        }
        
        return res;       // return cnt
    }

}; 

Complexity Analysis:

• Time Complexity: O(n log n)
• Space Complexity: O(1)