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:

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<>();
}

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();
* 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):
"""
"""
self.intervals = []

"""
: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()
# 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}
*/
//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()
* 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() {

}

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();
* 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;
}
});
}

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);
}
}

public IList GetIntervals() {
return new List(intervals);
}
}

/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();