Merging intervals variant question


  • 0
    R

    You are given an interface as below

    public interface MergeIntervals
    {
        /**
         * Adds the new interval to the list of intervals and merges the new list if possible
         */
        void addInterval(int from, int to);
    
        /**
         * Computes the sum of the difference between the each disjoint interval in the lnterval list
         */
        int getTotalIntervalCoverage();
    }
    

    The program proceeds as below

    For example, initially list is empty, and addInterval is called in the below order

    • list = [], totalIntervalCoverage = 0
    • addInterval(3, 6) -> list = [[3,6]] , totalIntervalCoverage = 3
    • addInterval(8, 9) -> list = [[3,6], [8,9]], totalIntervalCoverage = 3 + 1 = 4
    • addInterval(1, 5) -> list = [[1, 6], [8,9]], totalIntervalCoverage = 5 + 1 = 6

    For the above question, I came up with a LinkedList for maintaining intervals internally. Essentially, whenever a newInterval is added, skip all lesser than intervals. If a merge is possible, proceed until you can no longer merge, add it to the list and connect the "lesser than" section to the mergedInterval and the mergedInterval section to the greaterThan section.

    totalIntervalCoverage can be obtained by looping through the list and returning the sum of diff of each interval.

    addInterval and totalIntervalCoverage is O(n) in my case. Is there any better way to solve this question?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.