path: root/mergeintervals/main.go

/**

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()
}