adamgarcia4 · July 20, 2020 03:20
diff --git a/merged interval notes b/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.
	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.