intervals

interval primer

interval problems:

if you can solve these you can use them as abstractions to solve virtually any interval problem
with modifications

1) given a bunch of disjoint* intervals, and an interval you have, return the total # of units for the intersection of your interval
with the other intervals, note that these intervals are inclusive on points (DONE)
    https://nedbatchelder.com/blog/201310/range_overlap_in_two_compares.html
    the only way this works is if they are disjoint, if they are not disjoint merge them to be disjoint

    intervals = (200, 300), (300, 500), (550,600)
    intersect with (300,400) -> 102 units
    intersect with (250,400) -> 300-250+1+400-300+1 = 152 units
    intersect with (200,600) -> 353 units
    intersect with (520, 540) -> 0 units
    to intersect with (A,B) 

    input: interval (A,B)
    sort intervals from left to right by starting point X value where an interval is (X,Y)
    loop:
        from left to right find first interval with X such that X <= A
        figure out if entire interval (A,B) intersects (X,Y) completely, if it does return
        otherwise, intersection overlap is (max(X,A), min(Y,B)) = (Z,K)
            this means the overlap size is K-Z+1
            add K-Z+1 to your answer
        repeat with next interval

2) given a bunch of disjoint intervals, and an interval you have, intersect your interval with all the other intervals and 
produce a new list of intervals based on that (DONE)
    all you do is sort by left and right, then go through each interval, figure out if they intersect, if they do get
    the intersection, then push the intersection to a output list, otherwise ignore the interval if there is no overlap
    and repeat by comparing the considered interval with the intersection
        no you don't need a stack!! they are already all disjoint**
            i don't think you need to even overrride/replace the current interval because the intervals you are given are
            disjoint, so you can always just compute the intersection in O(1)
    assume all intervals are disjoint already**, if they aren't run merge k intervals first (which requires a stack)
    you can intersect multiple* intervals with your single interval
    sort input by start X

3) given an interval A, figure out if it overlaps with interval B (DONE)
    invert the "not overlaps" case

4) merge k intervals: given a list of non disjoint intervals, convert them to disjoint (merged) intervals (DONE)
    easy & straight forward, use a stack based approach after sorting by X
    overlap -> "is the start time of the current interval less than the end time of the previous interval?"
        then use a stack, take the top of the stack and merge it with the current interval, push the merged interval,
        repeat
            you don't even necessarily need to pop to merge, just adjust the endpoint
    make sure to not throw away intervals, just merge them. obv by throwing them out they become disjoint
    note thast the "does this interval overlap" check is simple
    https://leetcode.com/problems/merge-intervals/
    requires a stack

5) given a list of intervals wherew some overlap, find the maximal set of disjoint interval (DONE)
    https://www.geeksforgeeks.org/maximal-disjoint-intervals/
    O(nlogn), sort by endpoint, stems from the 2-1 observation which is that you can greedily/optimally
    at each step be processing a new interval with respect to a set of disjoint ones, but by sorting by
    end point you are guaranteeing you remove the interval that will cover more intervals with respect to its end point
    in the future
    only compare the current interval with the last interval for overlap (current interval left with last
    interval's right for overlap). if there is overlap, do not include the current interval, continue
        -> explanation: consider how the ordering changes when you process an interval by increasing endpoint, all the big intervals
        get processed later and if they have small endpoints/collide with earlier intervals they don't cause the removal
        of those intervals (we keep those intervals)
        -> use a stack and compare the last interval on the top of the stack for removal/adding
        -> O(1) solution possible just by storing right endpoitn

https://www.geeksforgeeks.org/check-if-any-two-intervals-overlap-among-a-given-set-of-intervals/
    this can be done in O(Nlogn) (requires sorting)