Question

Formatted question description: https://leetcode.ca/all/352.html

 Given a data stream input of non-negative integers a1, a2, ..., an, ...,
 summarize the numbers seen so far as a list of disjoint intervals.

 For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

 [1, 1]
 [1, 1], [3, 3]
 [1, 1], [3, 3], [7, 7]
 [1, 3], [7, 7]
 [1, 3], [6, 7]


 Follow up:

 What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?


 @tag-array
 @tag-interval

Algorithm

Use TreeMap

To get previous range last index, and next range first index. Then compare and decide if merge or not.

Integer l = tree.lowerKey(val);  // @note: Returns the greatest key strictly less than the given key

Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key

Interval start/end check

Every time a new number val comes in, a new interval [val, val] is generated, and an empty interval array res is created, and a variable cur is used to store the position of the new interval.

Traverse the existing interval array intervals, for each traversed current interval interval,

  • If the end position of the interval to be added plus 1 is smaller than the start position of the current interval, indicating that the two are not connected, add the current interval to res.
  • Otherwise, when the start position of the interval to be added is greater than the end position of the current position plus 1, it means that there is no intersection between the two, and the current interval can be added to res,
    • But at this time, cur should be incremented by 1 because the position to be added to the interval is behind the current interval.
  • Otherwise, the two will overlap and need to be merged,
    • At this time, use the smaller of the two starting positions to update the starting position of the interval to be added,
    • In the same way, use the larger of the two end positions to update the end position of the interval to be added.

Finally, the interval to be added is placed at the cur position in res, and then res is assigned to intervals

Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

  • lots of merges -> add() cannot be too costy
  • the number of disjoint intervals are small -> get() can be costy

to reduce cost of add(), use O(logn) for insertion of points (no merge), and maintain order get will have to calculate the disjoint intervals on the fly (basically lazy loading, do a merge on get() trigger)

Code

Java

import java.util.*;

public class Data_Stream_as_Disjoint_Intervals {

    public static void main(String[] args) {
        Data_Stream_as_Disjoint_Intervals out = new Data_Stream_as_Disjoint_Intervals();
        SummaryRanges s = out.new SummaryRanges();
//
//        ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals",
//            "addNum","getIntervals","addNum","getIntervals"]
//        [[],[1],[],[3],[],[7],[],[2],[],[6],[]]

//        s.addNum(1);
//        s.addNum(3);
//        s.addNum(7);
//        s.addNum(2);
////        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));
//        s.addNum(6);
//        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));

        s.addNum(49);
        s.addNum(97);
        s.addNum(53);
        s.addNum(5);
        s.addNum(33);
        s.addNum(65);
        s.addNum(62);
//        s.intervals.stream().forEach(i -> System.out.println(Arrays.toString(i)));
        int[][] r = s.getIntervals();
        System.out.println(Arrays.toString(s.getIntervals()));
    }

    public class SummaryRanges_TreeMap {

        // val to interval
        TreeMap<Integer, Interval> tree;

        public SummaryRanges_TreeMap() {
            tree = new TreeMap<>();
        }

        public void addNum(int val) {
            if(tree.containsKey(val)) {
                return;
            }

            Integer l = tree.lowerKey(val);  // @note: Returns the greatest key strictly less than the given key,
            Integer h = tree.higherKey(val); // @note: Returns the least key strictly greater than the given key

            if(l != null && h != null && tree.get(l).end + 1 == val && val + 1 == h) {
                tree.get(l).end = tree.get(h).end;
                tree.remove(h);
            } else if(l != null && tree.get(l).end + 1 >= val) {
                tree.get(l).end = Math.max(tree.get(l).end, val);
            } else if(h != null && h == val + 1) {
                tree.put(val, new Interval(val, tree.get(h).end));
                tree.remove(h);
            } else {
                tree.put(val, new Interval(val, val));
            }
        }

        public List<Interval> getIntervals() {
            return new ArrayList<>(tree.values());
        }
    }

    class SummaryRanges {
        PriorityQueue<int[]> intervals;
        List<int[]> resultTmp = new ArrayList<>();

        /** Initialize your data structure here. */
        public SummaryRanges() {
            intervals = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });
        }

        public void addNum(int val) {
            int[] newInterval = new int[]{val, val};
            List<int[]> result = new ArrayList<>();
            int newIntervalIndex = 0;

            for (int[] interval : resultTmp) {
                if (newInterval[1] + 1 < interval[0]) {
                    result.add(newIntervalIndex, interval);
//                    ++newIntervalIndex; // @note: right newIntervalIndex to insert
                } else if (newInterval[0] > interval[1] + 1) {
                    result.add(newIntervalIndex, interval);
                    ++newIntervalIndex;
                } else {
                    newInterval[0] = Math.min(newInterval[0], interval[0]);
                    newInterval[1] = Math.max(newInterval[1], interval[1]);
//                    result.add(newIntervalIndex, newInterval);
//                    ++resultPonter;
                }
            }

            result.add(newIntervalIndex, newInterval);
            resultTmp = result;

            intervals.clear();
            resultTmp.forEach(intervals::offer);

        }

        public int[][] getIntervals() {
            return intervals.toArray(new int[intervals.size()][]); // @note
        }
    }

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * int[][] param_2 = obj.getIntervals();
 */
}

All Problems

All Solutions