wordsHEADmain

1 files changed, 359 insertions, 0 deletions

diff --git a/mergeintervals/main.go b/mergeintervals/main.go
new file mode 100644
index 0000000..6e2a26e
--- /dev/null
+++ b/mergeintervals/main.go
@@ -0,0 +1,359 @@
+/**
+
+Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
+
+
+
+Example 1:
+
+Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
+Output: [[1,6],[8,10],[15,18]]
+Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
+
+Example 2:
+
+Input: intervals = [[1,4],[4,5]]
+Output: [[1,5]]
+Explanation: Intervals [1,4] and [4,5] are considered overlapping.
+
+Example 3:
+
+Input: intervals = [[4,7],[1,4]]
+Output: [[1,7]]
+Explanation: Intervals [1,4] and [4,7] are considered overlapping.
+**/
+
+package main
+
+import (
+	"fmt"
+	"math"
+	"math/rand/v2"
+)
+
+// func insertionIndex(time int) int {
+// low, high := 0, len(bucket.entries)
+// for low < high {
+// // Calculate mid carefully to prevent integer overflow
+// mid := low + (high-low)/2
+
+// if bucket.entries[mid].time <= time {
+// low = mid + 1
+// } else {
+// high = mid
+// }
+// }
+
+// return low
+// }
+
+type SkipNode struct {
+	val []int
+
+	prevs []*SkipNode
+	nexts []*SkipNode
+}
+
+type SkipList struct {
+	levels int
+	heads  []*SkipNode
+}
+
+func (l *SkipList) print() {
+	for i := len(l.heads) - 1; i >= 0; i-- {
+		head := l.heads[i]
+		fmt.Printf("[LIST %d]: ", i)
+		for head != nil {
+			fmt.Printf("[%d, %d]", head.val[0], head.val[1])
+			head = head.nexts[i]
+			if head != nil {
+				fmt.Print(", ")
+			}
+		}
+		fmt.Println()
+	}
+}
+
+const halfMax = math.MaxUint / 2
+
+func flip() bool {
+	return rand.Uint() > halfMax
+}
+
+func overlaps(lo, hi, mlo, mhi int) (overlaps bool, goLeft bool, goRight bool) {
+	overlaps, goLeft, goRight = false, false, false
+	// if lo < mlo && hi > mlo
+	// if hi > mhi and lo < mi
+	if (hi >= mhi && lo <= mhi) || (lo <= mlo && hi >= mlo) {
+		overlaps = true
+
+		if lo < mlo {
+			goLeft = true
+		}
+
+		if hi > mhi {
+			goRight = true
+		}
+	}
+
+	if hi < mlo {
+		goLeft = true
+	}
+
+	if lo > mhi {
+		goRight = true
+	}
+
+	return overlaps, goLeft, goRight
+}
+
+func (l *SkipList) insertInterval(interval []int) {
+
+	lo, hi := interval[0], interval[1]
+
+	debugcondition := lo == 5
+	nexts := l.heads
+	// overLappedNodes := make([]*SkipNode, l.levels)
+	lastVisitedPerLevel := make([]*SkipNode, l.levels)
+	level := l.levels - 1
+	var nodeOfNexts *SkipNode
+search:
+	for {
+		if level < 0 {
+			panic("whoops")
+		}
+		current := nexts[level]
+		if current == nil {
+			// we need to know where we came from T_T
+			// need to set last visited to node of nexts unless it's nil in which case, we are going to make new head
+			if nodeOfNexts != nil {
+				lastVisitedPerLevel[level] = nodeOfNexts
+			}
+			level = level - 1
+
+			if level < 0 {
+				level = 0
+				// we reached end of list 0, probably just do append routine somehow?
+				// MAYBE
+				current = lastVisitedPerLevel[0] // hopefully this results in tail node?
+				if current != nil && current.prevs[0] != nil {
+					nexts = current.prevs[0].nexts
+				}
+				if current == nil {
+					// edge case, all lists are empty here is our new head node
+					newNode := SkipNode{
+						val:   interval,
+						nexts: make([]*SkipNode, l.levels),
+						prevs: make([]*SkipNode, l.levels),
+					}
+					for {
+						if level >= l.levels {
+							break
+						}
+						var prev *SkipNode
+						if lastVisitedPerLevel[level] != nil {
+							prev = lastVisitedPerLevel[level].prevs[level]
+						}
+						if prev != nil {
+							prev.nexts[level] = &newNode
+						} else {
+							// new head
+							l.heads[level] = &newNode
+						}
+						newNode.prevs[level] = prev
+						if lastVisitedPerLevel[level] != nil {
+							lastVisitedPerLevel[level].prevs[level] = &newNode
+						}
+						newNode.nexts[level] = lastVisitedPerLevel[level]
+						level = level + 1
+					}
+
+					return
+				}
+
+				if current.nexts[0] != nil {
+					panic("very suspicious edge csae")
+				}
+			} else {
+				continue
+			}
+		}
+
+		mlo, mhi := current.val[0], current.val[1]
+
+		overlaps, goLeft, goRight := overlaps(lo, hi, mlo, mhi)
+		// @TODO FIRST goLeft is wrong, we need some like EITHER it says goLeft, which means goDown, or we have an overlap and we merge OR we go right which means we stay on same level and retry
+
+		if overlaps {
+			// MERGING / Go DOWN
+			// in this case we need to check the current level and see if a previous or next node belongs to the new merged range
+			// it's possible we would need to merge multipe intervals in a single insers so we probably need to keep going until no longer in the interval?
+
+			// TODO update current level node with new interval, explore in either direction for other affected nodes, continue until level == 0
+
+			return
+		}
+
+		if goLeft {
+			lastVisitedPerLevel[level] = nodeOfNexts // this needs to be node pointing TO next, which would be current.prevs[level]
+			// if ^ is nil, we know we came from the HEAD of the list, so we can go back to heads for that nonsense
+			// we know that we are not overlapping here and we know that hi < mlo, meaning we should go down
+			if level != 0 {
+				level = level - 1
+				continue
+			}
+			// can't go down, do push of new interval, NOT overlapping
+			// if we are on level 0, we have found the best node for new node to be inserted into
+			newNode := SkipNode{
+				val:   interval,
+				nexts: make([]*SkipNode, l.levels),
+				prevs: make([]*SkipNode, l.levels),
+			}
+			// insert inbetween prev and current
+			for {
+				if level != 0 && (!flip() || level >= l.levels) {
+					// not promoted
+
+					if !debugcondition {
+						break
+					}
+					if level == l.levels {
+						break
+					}
+				}
+				var prev, next *SkipNode
+				if lastVisitedPerLevel[level] != nil {
+					prev = lastVisitedPerLevel[level]
+				}
+
+				if prev != nil {
+					next = prev.nexts[level]
+					prev.nexts[level] = &newNode
+				} else {
+					// new head
+					next = l.heads[level]
+					l.heads[level] = &newNode
+				}
+				newNode.nexts[level] = next
+
+				if lastVisitedPerLevel[level] != nil {
+					lastVisitedPerLevel[level].nexts[level] = &newNode
+				}
+				newNode.prevs[level] = lastVisitedPerLevel[level]
+				level = level + 1
+			}
+			break search
+		} else if goRight {
+			// so in case of going right we need to set new nexts to next nodes nexts, and continue, do NOT go down
+			// if next on current level != nil, however if we are on level 0 and next is nil, we know we are doing a tail node append
+			// if we cannot go down, we need to insert node into best spot of list 0 and decide promotion
+			nexts = current.nexts
+			lastVisitedPerLevel[level] = current // this avoids edge case of landing on list 0 tail node and beign force to find tail node from list I think
+			nodeOfNexts = current
+			if level == 0 && nexts[0] == nil {
+				// EDGE CASE, we are at the end of the list 0 do NOT continue back to search, do append
+			} else {
+				continue search
+			}
+
+			// the only time we hit this case is when we have landed on a tail node of list 0
+
+			// do insert
+			newNode := SkipNode{
+				val:   interval,
+				nexts: make([]*SkipNode, l.levels),
+				prevs: make([]*SkipNode, l.levels),
+			}
+			// insert inbetween next and current
+			for {
+				if level != 0 && (!flip() || level >= l.levels) {
+					// not promoted
+					if !debugcondition {
+						break
+					}
+					if level == l.levels {
+						break
+					}
+				}
+
+				var next, prev *SkipNode
+				if lastVisitedPerLevel[level] != nil {
+					prev = lastVisitedPerLevel[level]
+					next = lastVisitedPerLevel[level].nexts[level]
+				} else {
+					panic("i don't think this is possible")
+				}
+				if next != nil {
+					next.prevs[level] = &newNode
+				}
+
+				newNode.nexts[level] = next
+
+				if lastVisitedPerLevel[level] != nil {
+					lastVisitedPerLevel[level].nexts[level] = &newNode
+				}
+				newNode.prevs[level] = prev
+				level = level + 1
+			}
+			break search
+		}
+	}
+}
+
+func merge(intervals [][]int) [][]int {
+	out := make([][]int, len(intervals))
+	out[0] = intervals[0]
+	outlen := 1
+
+	for _, interval := range intervals[1:] {
+		lo, hi := interval[0], interval[1]
+
+		slo, shi := 0, outlen
+		for slo < shi {
+			mid := slo + (shi-slo)/2
+
+			mlo, mhi := out[mid][0], out[mid][1]
+
+			if lo <= mhi || hi >= mlo {
+				// MERGING
+
+				break
+			}
+			if hi < mlo {
+				shi = mid
+			} else {
+				slo = mid + 1
+			}
+		}
+		// no overlap
+
+	}
+
+	return out[:outlen]
+}
+
+func main() {
+	l := SkipList{
+		levels: 4,
+		heads:  make([]*SkipNode, 4),
+	}
+
+	l.insertInterval([]int{9, 10})
+	l.print()
+	fmt.Println("inerting 3,4")
+	l.insertInterval([]int{3, 4})
+	l.print()
+	fmt.Println("inerting 7,8")
+	l.insertInterval([]int{7, 8})
+	l.print()
+	fmt.Println("inerting 5,6")
+	l.insertInterval([]int{5, 6})
+	l.print()
+	fmt.Println("inerting 11,12")
+	l.insertInterval([]int{11, 12})
+	l.print()
+
+	fmt.Println("inerting 1,2")
+	l.insertInterval([]int{1, 2})
+	l.print()
+}