Solution For Data Stream As Disjoint Intervals

Problem Statement:

Given an integer stream, we must maintain a running list of disjoint intervals and we must be able to insert a new integer into the stream at any time. Whenever a new integer is inserted into the stream, we must output the newly formed list of disjoint intervals.

Example:

Input:
insert(1), Output: [1,1] insert(3), Output: [1,1],[3,3] insert(7), Output: [1,1],[3,3],[7,7] insert(2), Output: [1,3],[7,7] insert(10), Output: [1,3],[7,7],[10,10],[12,16]

Solution:

We start with an empty list of disjoint intervals. Whenever a new integer is inserted into the stream, we check if it can be merged with any of the existing intervals. If merging is possible, we merge the intervals. If not, we add the interval as a new disjoint interval.

We can use a list of tuples to represent the disjoint intervals where each tuple represents an interval with a start and an end value.

Algorithm:

1. Start with an empty list of disjoint intervals.
2. Loop through the integer stream:
   1. Check if the integer can be merged with any of the existing intervals:
      1. If merged, update the merged interval.
      2. If not merged, add the current interval as a new disjoint interval.
   2. Sort the disjoint intervals based on their start value.
   3. Output the current list of disjoint intervals.

Python Code:

class Interval:
def init(self, start, end):
self.start = start
self.end = end

def insert(interval, num):
#check if num can be merged with any of the intervals
for i in range(len(interval)):
if num >= interval[i].start and num <= interval[i].end:
return #num is already within an interval
if num == interval[i].start – 1:
interval[i].start = num
return #merged with previous interval
elif num == interval[i].end + 1:
interval[i].end = num
#check if merged with the next interval also
if i < len(interval)-1 and interval[i].end == interval[i+1].start – 1:
interval[i].end = interval[i+1].end
interval.pop(i+1)
return #merged with next interval
elif num < interval[i].start – 1:
interval.insert(i, Interval(num, num))
return #new interval inserted in the list
interval.append(Interval(num, num)) #all intervals merged, add as a new interval

def disjoint_intervals(nums):
intervals = [] for num in nums:
insert(intervals, num)
#sort the intervals based on their start value
intervals.sort(key = lambda x: x.start)
#print the current list of disjoint intervals
print([[i.start, i.end] for i in intervals])

Test Case

disjoint_intervals([1,3,7,2,10]) #expected output: [[1,3],[7,7]], [[10,10]]

Step by Step Implementation For Data Stream As Disjoint Intervals

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class SummaryRanges {
    
    TreeMap map;

    /** Initialize your data structure here. */
    public SummaryRanges() {
        map = new TreeMap<>();
    }
    
    public void addNum(int val) {
        if(map.containsKey(val)) return;
        Integer l = map.lowerKey(val);
        Integer h = map.higherKey(val);
        if(l != null && h != null && map.get(l).end + 1 == val && h == val + 1) {
            map.get(l).end = map.get(h).end;
            map.remove(h);
        } else if(l != null && map.get(l).end + 1 >= val) {
            map.get(l).end = Math.max(map.get(l).end, val);
        } else if(h != null && h == val + 1) {
            map.put(val, new Interval(val, map.get(h).end));
            map.remove(h);
        } else {
            map.put(val, new Interval(val, val));
        }
    }
    
    public List getIntervals() {
        return new ArrayList<>(map.values());
    }
}

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

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class SummaryRanges(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.intervals = []

    def addNum(self, val):
        """
        :type val: int
        :rtype: void
        """
        if not self.intervals:
            self.intervals.append(Interval(val, val))
            return
        
        # find the insert position
        left, right = 0, len(self.intervals) - 1
        while left <= right:
            mid = (left + right) / 2
            if self.intervals[mid].start <= val <= self.intervals[mid].end:
                return # the interval already exists
            elif val < self.intervals[mid].start:
                right = mid - 1
            else:
                left = mid + 1
        
        # insert the interval
        if val == self.intervals[left].start - 1:
            self.intervals[left].start = val
        elif val == self.intervals[right].end + 1:
            self.intervals[right].end = val
        else:
            self.intervals.insert(left, Interval(val, val))

    def getIntervals(self):
        """
        :rtype: List[Interval]
        """
        return self.intervals

# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(val)
# param_2 = obj.getIntervals()

/**
 * Definition for an interval.
 * function Interval(start, end) {
 *     this.start = start;
 *     this.end = end;
 * }
 */

/**
 * @param {Interval[]} intervals
 * @return {Interval[]}
 */
var SummaryRanges = function() {
    this.intervals = [];
};

/** 
 * @param {number} val
 * @return {void}
 */
SummaryRanges.prototype.addNum = function(val) {
    //edge case: if intervals is empty, just push val into it
    if(this.intervals.length === 0){
        this.intervals.push(new Interval(val, val));
        return;
    }
    
    //binary search to find the insert position
    let left = 0;
    let right = this.intervals.length - 1;
    let insertPos;
    
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        if(this.intervals[mid].start === val){
            return;
        } else if(this.intervals[mid].start < val && this.intervals[mid].end >= val){
            return;
        } else if(this.intervals[mid].start > val){
            right = mid - 1;
            insertPos = mid;
        } else {
            left = mid + 1;
            insertPos = mid + 1;
        }
    }
    
    //insert into intervals
    this.intervals.splice(insertPos, 0, new Interval(val, val));
    
    //merge if necessary
    if(insertPos > 0 && this.intervals[insertPos - 1].end + 1 >= val){
        this.intervals[insertPos - 1].end = Math.max(this.intervals[insertPos - 1].end, this.intervals[insertPos].end);
        this.intervals.splice(insertPos, 1);
    }
    
    if(insertPos < this.intervals.length - 1 && this.intervals[insertPos + 1].start - 1 <= val){
        this.intervals[insertPos].end = Math.max(this.intervals[insertPos].end, this.intervals[insertPos + 1].end);
        this.intervals.splice(insertPos + 1, 1);
    }
};

/**
 * @return {Interval[]}
 */
SummaryRanges.prototype.getIntervals = function() {
    return this.intervals;
};

/** 
 * Your SummaryRanges object will be instantiated and called as such:
 * var obj = Object.create(SummaryRanges).createNew()
 * obj.addNum(val)
 * var param_2 = obj.getIntervals()
 */

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class SummaryRanges {
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
        
    }
    
    void addNum(int val) {
        auto it = ints.lower_bound(Interval(val, val));
        int start = val, end = val;
        if (it != ints.begin() && (--it)->end + 1 < val) it++;
        while (it != ints.end() && val + 1 >= it->start && val - 1 <= it->end) {
            start = min(start, it->start);
            end = max(end, it->end);
            it = ints.erase(it);
        }
        ints.insert(it, Interval(start, end));
    }
    
    vector getIntervals() {
        return vector(ints.begin(), ints.end());
    }
private:
    set ints;
};

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

/**
 * Definition for an interval.
 * public class Interval {
 *     public int start;
 *     public int end;
 *     public Interval() { start = 0; end = 0; }
 *     public Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class SummaryRanges {

    private TreeSet intervals;
    
    /** Initialize your data structure here. */
    public SummaryRanges() {
        intervals = new TreeSet(new Comparator(){
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
        });
    }
    
    public void AddNum(int val) {
        if(intervals.contains(new Interval(val,val))){
            return;
        }
        Interval interval = new Interval(val,val);
        Interval floor = intervals.floor(interval);
        Interval ceil = intervals.ceiling(interval);
        if(floor != null && floor.end >= val){
            return;
        }
        if(ceil != null && ceil.start <= val){
            interval.start = floor.start;
            interval.end = ceil.end;
            intervals.remove(floor);
            intervals.remove(ceil);
        }
        if(floor != null && floor.end == val - 1){
            interval.start = floor.start;
            intervals.remove(floor);
        }
        if(ceil != null && ceil.start == val + 1){
            interval.end = ceil.end;
            intervals.remove(ceil);
        }
        intervals.add(interval);
    }
    
    public IList GetIntervals() {
        return new List(intervals);
    }
}

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.AddNum(val);
 * IList param_2 = obj.GetIntervals();
 */