Buttercola: LinkedIn: Add Interval

Buttercola: LinkedIn: Add Interval
http://needjobasap.blogspot.com/2015/05/l-question-get-interval-range.html

public interface Intervals {

    /**

     * Adds an interval [from, to] into internal structure.

     */

    void addInterval(int from, int to);

    /**

     * Returns a total length covered by intervals.

     * If several intervals intersect, intersection should be counted only once.

     * Example:

     *

     * addInterval(3, 6)

     * addInterval(8, 9)

     * addInterval(1, 5)

     *

     * getTotalCoveredLength() -> 6

     * i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]

     * [1,6] and [8,9] don't intersect so total covered length

     * is a sum for both intervals, that is 6.

     *

     *                   _________

     *                                               ___

     *     ____________

     *

     * 0  1    2    3    4    5   6   7    8    9    10

     *

     */

    int getTotalCoveredLength();

}

Use a list to store the intervals. 
 -- add(), add into the end of the list, so the complexity is O(1).
 -- getLength(), very similar to the merge interval. First sort the list of intervals, find the longest overlapped interval and calculate the length. The complexity is O(nlogn). 

public class Solution {

    private List<Interval> intervals = new ArrayList<>();

    /**

     * Adds an interval [from, to] into internal structure.

     */

    void addInterval(int from, int to) {

        Interval interval = new Interval(from, to);

        intervals.add(interval);

    }

    /**

     * Returns a total length covered by intervals.

     * If several intervals intersect, intersection should be counted only once.

     * Example:

     *

     * addInterval(3, 6)

     * addInterval(8, 9)

     * addInterval(1, 5)

     *

     * getTotalCoveredLength() -> 6

     * i.e. [1,5] and [3,6] intersect and give a total covered interval [1,6]

     * [1,6] and [8,9] don't intersect so total covered length

     * is a sum for both intervals, that is 6.

     *

     *                   _________

     *                                               ___

     *     ____________

     *

     * 0  1    2    3    4    5   6   7    8    9    10

     *

     */

    int getTotalCoveredLength() {

        if (intervals.isEmpty()) {

            return 0;

        }

         

        Collections.sort(intervals, new IntervalComparator());

         

        int len = 0;

         

        Interval prev = intervals.get(0);

         

        for (int i = 1; i < intervals.size(); i++) {

            Interval curr = intervals.get(i);

             

            if (overlaps(prev, curr)) {

                prev.start = prev.start;

                prev.end = Math.max(prev.end, curr.end);

            } else {

                len += prev.end - prev.start;

                prev = curr;

            }

        }

        //X after for loop

        len += prev.end - prev.start; // Be very careful to check this case.

         

        return len;

    }     

    private class IntervalComparator implements Comparator<Interval> {

        @Override

        public int compare(Interval a, Interval b) {

            return a.start - b.start;

        }

    }

     

    private boolean overlaps(Interval prev, Interval curr) {

        return prev.end > curr.start;

    }

}

http://blog.csdn.net/craiglin1992/article/details/44759403
public class MyIntervals implements Intervals { List<Length> l = new LinkedList<Length>(); @Override public void addInterval(int from, int to) { l.add(new Length(x,y)); } @Override public int getTotalCoveredLength { Collections.sort(l); int retLength = 0; Length lastone = new Length(0,0); for(Length len : l) { if(len.x > lastLen.y) {//locate apart totalLen += len.y - len.x; lastLen = len; } else if(len.y >lastlen.y) { //overlapping totalLen += len.y-lastLen.y; lastLen = len; } //注意这里不需要考虑如果后一个在前一个里面会怎么样，因为lastLen会维持一样，写一次仍然跟前一个做比较 } return totalLen; } } public class Length implements Comparable<Length> { public int x, y; public Length(int x, int y) { this.x = x; this.y = y; } @Override public compareTo(Length o) { if(o.x-this.x == 0) { return 0; } if(o.x-this.x > 0) { return -1; } if(o.x-this.x < 0) { return 1; } } }
http://www.careercup.com/question?id=5711223014293504
Read full article from Buttercola: LinkedIn: Add Interval