Interval List Merging

Given two lists of disjoint intervals intervals1 and intervals2, where each interval is a closed interval [start, end], write a function to return their intersection, also a list of closed intervals. The intervals in the output must also be sorted in ascending order by their start times. Your algorithm should run in O(N) time complexity. Test Case: Input: intervals1 = [[1,3],[5,9]], intervals2 = [[2,4],[6,8]] Output: [[2,3],[6,8]] Input: intervals1 = [[1,2],[3,5],[6,7],[8,10],[12,16]], intervals2 = [[4,8]] Output: [[4,5],[6,7],[8,8]] Note: The input interval lists are sorted by the start time. Example Input [[1,3],[5,9]] [[2,4],[6,8]]