merged interval notes

Interval Operations

There are a few operations that can be performed on intervals:
1. Merge  interval[] s.t. the all intervals are disjoint.
		[0,5],[5,7] ==> [0,7]
2. Insert interval into interval[] s.t. all intervals are disjoint.
3. Find intersection between two interval[].
		[0,5],[5,7] => [5,5]

In order to perform these operations, it is important to understand the 6
different ways in which two intervals can relate to one another.

These can be further subdivided into three categories.

===== Categories ========
1. No Overlap
2. Partial Overlap
3. Full Overlap

== No Overlap ==
Trivially, A can finish before B starts, or the other way around.
1. A comes before B
		[0,5], [7,10]
		[0,5], [6,10] Threshold
		-------
					 --------
		Condition: a.end < b.start
# 2. B comes before A (Doesn't matter so much, because A is)
#		[7,10], [0,5]
#							--------
#		-------
#		a.start >= b.end and a.end > b.end

== Parital Overlap ==
  Desc: start of an interval is between the start/end of the other interval
3. 'B' ends after 'A'
		[0,5], [2,7]
		-------
		    ------

		Condition: a.start <= b.start and b.start <= a.end
							a.start <= b.start <= a.end
4. 'A' ends after 'B'
		[2,7], [0,5]
		    ------
		-------
		
		Condition: a.start >= b.start and a.start <= b.end
							b.start <= a.start <= b.end
== Complete Overlap ==
5. A completely overlaps B.
		[0,5], [2,4]
    --------
		   ---

6. B completely overlaps A.
		[2,4], [0,5]
		   ---
		--------

===== Interval Operations ========

There are two valid operations that can be done on two overlapping intervals.
1. Merge
2. Intersection

Important to algorithmic problems is the interval AFTER the operation
1. Merge (1 list) - Union
		newStart = min(a.start, b.start) ==> a.start
		newEnd = max(a.end, b.end)
2. Intersection - Intersection
		newStart = max(a.start, b.start)
		newEnd = min(a.end, b.end)


===== Algorithmic Understanding ========
With this background in mind, it is now possible to structure an algorithm 
after these two operation types.

1. LC: 56 - Merge Intervals
2. LC: 57 - Insert Intervals
3. LC: 986 - Interval List Intersections

== Merge Interval ==

Continue to grow the merged interval until there is a disjoin.
Then you commit this, and reset the merged interval to this disjoined event.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        
        a = [None, None]
        res = []
        for i in range(len(intervals)):
            b = intervals[i]
            if i == 0:
                a = b
                continue
            
            # Check for overlap
            if a[0] <= b[0] <= a[1]:
                # Grow the interval as big as it can get
                newStart = a[0]
                newEnd = max(a[1], b[1])
                a = [newStart, newEnd]
            else:
                # There is a disjoin.
                res.append(a)
                a = b
        
        if a[0] == None:
            return []
        res.append(a)
        return res

== Insert Interval ==

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i = 0
        
        # skip all intervals that come before the new interval
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1
        
        # at this point, intervals[i]'s end > start of new interval.
        a = newInterval
        while i < len(intervals) and intervals[i][0] <= a[1]:
            b = intervals[i]
            
            newStart = min(b[0], a[0])
            newEnd = max(b[1], a[1])
            
            a = [newStart, newEnd]
            
            i += 1
        # This represents the merged interval that includes the new interval AND all subsequent overlapping intervals
        res.append(a)
        
        # Put the rest of the intervals into the result.
        while i < len(intervals):
            res.append(intervals[i])
            i += 1
        return res

Ask Interviewer
		Ask interviewer if side-by-side is considered overlapping.