435. Non Overlapping Intervals(IMPORTANT DEDUCTION)

//VISIT THIS for more understanding - https://chatgpt.com/share/6885b96b-4234-8012-a95a-7a1075632caf
class Solution {
public:
    //This question can't be solved using LIS version as written below because of the following reason -
    //AS both axis are dependent on each other
    //end[nextLevel] >= start[currentLevel]
    //The property spans over both the axis simultaneously due to which it is hard to make them independent.
    //INDEPENDENT MEANS -
    //SORT 1 axis (make it monotonic)
    // USE LIS on other (take different monotonic sequence(here increasing) in AXIS 2, when ordered in ABSOLUTE MONOTONIC ORDER of AXIS 1)
    // but the axis here are dependent on each other

    /*
    -----I----------------I-------------I----- AXIS 1
          I              I             I
           I            I             I
            I          I             I
             I        I             I
    ----------I------I-------------I----------- AXIS 2


    If the diagram looks like this in(non overlapping bridges, russian doll envelopes), we consider it a variation of LIS where we apply LIS on 1 axis when BOTH the AXIS are in SORTED IN MONOTONIC ORDER of 1 AXIS.

    --------------------------------------------------------------------------------------------
                    [start1]--------------------[end1]
    [s2]--------e[2]                                  [s3]-------------[e3]
                    [s4]----------[e4]                        [s5]-----[e5] [s6]--------------[e6]


    Here both the axis are represented in a single combined axis from [start] ------[end].
    Which means the both the axis are dependent on each other as they are represented in a single axis
    It is what is present in the question such as non overlapping intervals(LC version), projects (cses), weighted scheduling problem[LC]

    here we see a dependency between the axis in the form of a conditional that interleaves both the values such as in Non overlapping intervals question, conditional used =>
    if Current Level included, then jump to a level that satisfies start[nextLevel] >= end[currentLevel]

    [[1,2],[1,3],[2,3],[3,4]] for this test case

    LIS VARIATION/AXES INDEPENDENT (Russian doll or Non Overlapping Bridges(GFG))
    The answer would be 4, as all are non overlapping in nature. {[1,2], [1, 3], [2, 3], [3, 4]}

    JUMP DP/AXES DEPENDENT(Non Overlapping Intervals(LC), Projects(CSES), Weighted Scheduling Problem(LC))
    The answer would be 3, as 3 are non overlapping in nature {[1,2], [2, 3]. [3, 4]}

    Draw Diagram, would be easy to notice.

    */
    int getMaxOverlap(int level, vector<vector<int> > &intervals){
        int maxLength = 0;
        bool flag = false;

        for(int i = level + 1; i < intervals.size(); i++){
            //indicates the loop ran ATLEAST ONCE
            flag = true;
            //LIS condition, ONLY CALL TO LEVELS THAT ARE VALID
            //VALID LEVELS, any nextLevel that follows the property => END[nextLevel] >= END[level]
            if(intervals[i][1] >= intervals[level][1]){
                maxLength = max(maxLength, 1 + getMaxOverlap(i, intervals));
            }
        }
        //if loop didn't run, the value of current valid level never got added as it happens inside loop => 1 + recursive call
        // ADD it EXPLCITLY to the maxLength;
        //return flag == true ? maxLength : maxLength + 1;

        //OR you could simply return the value of current level, i.e. 1
        // AS there were no further levels which were valid relative to the current level, the maxLength of the chain that can be formed from  range[level, intervals.size() - 1], INCLUDING level is 1 (current level itself is chain of length 1)

        return flag == true ? maxLength : 1;
    }

    //LIS VERSION
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        //sort the intervals to remove dependency from start, NO NEED TO TRACK START as they always increase
        //START is always increasing, so start[level + 1] >= start[level], which makes OVERLAP of intervals impossible based on START as they are always increasing/of monotonic nature.
        sort(intervals.begin(), intervals.end());

        //USE LIS on END
        //So for END[level] we need to figure what is maximum increasing sequence when ORDERED in INCREASING ORDER of start times.
        //IMPORTANT
        // 2 AXIS where both AXIS work INDEPENDENTLY

        // WE SORT THE FIRST AXIS (introduces monotonicity in that axis, ALWAYS INCREASING)
        // WE DO LIS on SECOND AXIS (for monotonic first axis, find maximum length in 2nd AXIS)
        int maxLength = 0;
        //give every interval the chance to be the first in the sequence
        for(int i = 0; i < n; i++){
            maxLength = max(maxLength, getMaxOverlap(i, intervals));
        }
        return n - maxLength;
    }
};

/*
//BEST APPROACH TO DO IT (JUMP DP QUESTION)
//JUMP DP QUESTIONS ARE THOSE QUESTIONS WHERE AXES ARE DEPENDENT ON EACH OTHER/CONDITIONAL WRITTEN INCLUDES element //FROM BOTH THE AXES.
//such as start[nextLevel] >= end[currentLevel]
//THEY ARE DIFFERENT FROM LIS BASED QUESTION, where 1 axis is sorted to make it monotonic and on the other AXIS LIS is //applied.

class Solution {
public:

    //finding the next OPTIMAL start point O(N)
    int findNextLevel(int level, vector<vector<int> > &intervals){
        for(int i = level + 1; i < intervals.size(); i++){
            //next VALID level is the FIRST/CLOSEST level with property start[nextLevel] >= end[level]
            if(intervals[level][1] <= intervals[i][0]){
                return i;
            }
        }
        //if there is no next valid after current level, return the index = intervals.size(), SIGNIFYING all the intervals have been processed, and it gets CATCHED in the BASE CASE
        return intervals.size();
    }

    //O(log(n)) time to find next valid level
    int findNextLevelBS(int level, vector<vector<int> > &intervals){
        int l = level + 1, r = intervals.size() - 1, idx = intervals.size();
        while(l <= r){
            int mid = (l + r) / 2;
            //if the start[mid] >= end[currentLevel], valid level found, save and search for better
            if(intervals[mid][0] >= intervals[level][1]){
                idx = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        //if bs ran, it would return the MOST OPTIMAL level(A level with interval which has a start JUST LARGER than the end of current level), if it didn't run, it would return intervals.size(), signifying that all the intervals that could be processed are already processed, now we reach base case.
        return idx;
    }

    int getMaxOverlap(int level, vector<vector<int> > &intervals, vector<int> &memo){
        if(level >= intervals.size()){
            return 0;
        }
        if(memo[level] != -1){
            return memo[level];
        }
        int inc = 0, exc = 0;
        //include the current level, increase chain by 1, move to the next VALID level
        int nextLevel = findNextLevelBS(level, intervals);
        inc = 1 + getMaxOverlap(nextLevel, intervals, memo);

        //next level is automatically valid if current excluded as start[level + 1] >= start[level]
        exc = getMaxOverlap(level + 1, intervals, memo);

        return memo[level] = max(inc, exc);
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        //memo key = memo(level) as it is the ONLY variable that is changing, influencing either the base case or transition logic (here base case), and not derivable
        //memo(level) => range of level{0, 1, 2, 3, 4 .......n} => memo[n]
        vector<int> memo(n, -1);
        //ALTHOUGH we are only jumping to VALID LEVELS, still the complexity of code in worst case would be
        //T.C. = O(N*log(N)) and S.C. = O(N)
        //As there can be at max N levels in wors case(all non overlapping) and at each level log(N) work is done
        //So the total complexity would be total unique states * work at each level
        //N * log(N)
        return intervals.size() - getMaxOverlap(0, intervals, memo);
    }
};
*/