Data stream as disjoint intervals


  • 0
    Y

    Given a data stream input of positive integers a1, a2, ..., an, ..., summary the numbers seen so far as a list of disjoint intervals.

    For example, suppose the input 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]

    Need to do it better than linear time.


  • 0
    Y

    How to make it as a leetcode problem?


  • 0

    Why there is no range {1,1},{3,7}


  • 0
    Y

    @elmirap interval [3,7] should contain numbers with 3,4,5,6,7.


  • 0

    I see, thanks.Is it possible stream to contain duplicates?


  • 0

    @yunhong Interesting. This problem is similar to Summary Ranges, except that it is expressed in a stream format. Also, the integers in the stream is not sorted.


  • 0

    Since the intervals are disjoint (non-overlapping), this problem can be solved efficiently with using Binary Search Tree. For overlapping intervals, you have to use Interval Tree.


  • 1

    Well, BST could not do the merging of intervals efficiently. I would say just use Binary Search to find the intervals to merge, which is possible in O(log n). By inserting a point to a list of sorted disjoint intervals, it would cause at most two intervals to be merged. So you only need to look at the interval before and after it.


  • 0
    Y

    @elmirap yes, duplicates are allowed


  • 0
    Y

    @1337c0d3r Merging adjacent intervals or inserting an interval takes linear time, for an array / list. For doubly connected list, insertion or merge takes constant time, however finding the interval takes linear time. So BST is the choice that makes all operations O(log n).


  • 1

    @1337c0d3r ,I was thinking the same. But the problem is that to use BS effectively you need array, also there is dynamic in the problem (not by accident this is a stream), we insert numbers and we have to rearrange them in the proper place. With BST, I think that we have to search where to insert the number and check its left and right neighbour always. In the worst case we have to merge both intervals (left and right), this need to delete one node of the tree which is again log(n) operation
    As you mentioned, the problem is easier because intervals dont overlapp


  • 0

    Need to do it better than linear time.

    What does this mean? Each insert? Get interval?


  • 0

    @xidui I assume it's each insert. You can assume that you have a function called:

    List<Interval> insert(int val)
    

    Each insert call will return the current summary ranges.


  • 0

    @xidui yes, I assume that we have a lot of memory ,and insert should be logarithmic, and there is stream....I am curious to which SDE is pointed the question - SDE 1, 2 ,3


  • 0

    @elmirap However is it possible to have logarithmic time when the function signature returns a List<Interval>?


  • 0

    @1337c0d3r I think insert should be logarithmic, sorry Actually I believe that there are two functions - for insert and read intervals


  • 0

    @elmirap As @yunhong mentions, using a BST enables all operations to complete in O(log n). Then you will need to return the root of the tree, not List<Interval>. I don't think it's possible to do insert in O(log n) if your function signature has to return List<Interval>.


  • 0

    @1337c0d3r
    I agree with @elmirap that there may be two functions: "insert" and "get interval".
    Complexity of "insert" is O(log n) while "get interval" is O(n).


  • 0

    @xidui Oh ya, that makes perfect sense, thanks!


  • 0

    @1337c0d3r Yes, if our function return List<Interval> you are actually right


Log in to reply
 

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