Problem
Find non overlapping intervals?
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
-----------
---- ---- ----
--|----|----|----|--
1 2 3 4
O/P (Non overlapping intervals): 3
[1,2],[2,3],[3,4]
Step by Step Algorithm
1. Sort the intervals based on their end times(or start times, depending on the problem).
input intervals = [[1,2],[2,3],[3,4],[1,3]]
sorted intervals = [[1,2],[2,3],[1,3],[3,4]]
2. Take temp as 1st pair
temp = [1,2]. a1=1, b1=1
3. Iterate through the sorted intervals from i=1
i=1 a2=2, b2=3
if (b1 > a2)
- This is overlapping interval
else
b1 = b2 //point a to next element, because we need to reach element where b1 > a2