Linkedin Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
public class IntervalCollection {
int lowesrtLowerBound;//Stores the lowest lower bould in collection
int highestUpperBound;//Stores highest upper bound in collection.
List<Interval> intervalList = new ArrayList<Interval>();
public void insertInterval(int lowerBound, int upperBound) {
if (lowerBound >= upperBound) {
System.out.println("Invalid input");
return;
}
Interval interval = new Interval(lowerBound, upperBound);
if (intervalList.size() == 0) {
System.out.println("Base case");
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
if (lowerBound <= lowesrtLowerBound && upperBound >= highestUpperBound) {
System.out.println("Interval that covers all other intervals in the list");
intervalList.clear();
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
Interval mergeCandidate1 = null;
Interval mergeCandidate2 = null;
for (Interval in : intervalList) {
if (in.equals(interval))
return;//Duplicate
if (mergeCandidate1 == null && in.lowerBound <= lowerBound) {
mergeCandidate1 = in;
}
if (mergeCandidate2 == null && in.upperBound >= upperBound) {
mergeCandidate2 = in;
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
break;
}
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
System.out.println("Merge candidates identified");
Interval i = new Interval(mergeCandidate1.lowerBound, mergeCandidate2.upperBound);
intervalList.add(i);
updateLowestAndHighest(i.lowerBound, i.upperBound);
intervalList.remove(mergeCandidate1);
intervalList.remove(mergeCandidate2);
} else {
System.out.println("Adding a new item");
intervalList.add(interval);
}
}
private void updateLowestAndHighest(int lowerBound, int upperBound) {
if (lowerBound < lowesrtLowerBound) {
lowesrtLowerBound = lowerBound;
}
if (upperBound > highestUpperBound) {
highestUpperBound = upperBound;
}
}
Here is an O(n) algorithm assuming the intervals aren't guaranteed to be in sorted order. If they are then you can of course speed it up by doing binary search, as per Rohit, instead of a linear scan but the thought is the same. In C++:
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
void interval(std::vector<std::pair<int, int>> &a, std::pair<int, int> interv) {
int j = -1, k = -1;
int min = std::numeric_limits<int>::max();
int max = std::numeric_limits<int>::min();
for (int i = 0; i < a.size(); ++i) {
if (interv.first <= a[i].second && a[i].second < min) {
k = i;
min = a[i].second;
}
if (interv.second >= a[i].first && a[i].first > max) {
j = i;
max = a[i].first;
}
}
if (j == -1 || k == -1) {
a.push_back(interv);
return;
}
auto i = a.begin();
a[std::max(k, j)].first = std::min(a[k].first, interv.first);
a[std::max(k, j)].second = std::max(a[j].second, interv.second);
if (k != j) {
for (int v = std::min(k, j); v > 0; --v, i++);
a.erase(i);
}
}
int main() {
std::vector<std::pair<int, int>> a = {
std::pair<int, int>(0, 2), std::pair<int, int>(-10, -1), std::pair<int, int>(4, 10), std::pair<int, int>(14, 19), };
interval(a, std::pair<int, int>(-5, 1));
std::cout << "Adding [-5,1]:\n";
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [3,9]:\n";
interval(a, std::pair<int, int>(3, 9));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [1,3]:\n";
interval(a, std::pair<int, int>(1, 3));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-15,13]:\n";
interval(a, std::pair<int, int>(-15, 13));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-3,21]:\n";
interval(a, std::pair<int, int>(-3, 21));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [30, 50]:\n";
interval(a, std::pair<int, int>(30, 50));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << std::endl;
}
Can you please outline your algo in word or psuedo code ? I am not very familiar with C++
for (int i = 0; i < a.size(); ++i) {
if (interv.first <= a[i].second && a[i].second < min) {
k = i;
min = a[i].second;
}
if (interv.second >= a[i].first && a[i].first > max) {
j = i;
max = a[i].first;
}
}
if (j == -1 || k == -1) {
a.push_back(interv);
return;
}
This is the following:
Find the index into the array such that the lower bound on added interval is less than the upper bound on of another interval. If it's less than more than one interval, take the one with the minimum upper bound.
At the same time, find the index into the array such that the upper bound on the added interval is greater than the lower bound of another interval. If it is greater than more than one interval, take the maximum lower bound.
If no such interval exists, simply add the new interval to the array.
auto i = a.begin();
a[std::max(k, j)].first = std::min(a[k].first, interv.first);
a[std::max(k, j)].second = std::max(a[j].second, interv.second);
if (k != j) {
for (int v = std::min(k, j); v > 0; --v, i++);
a.erase(i);
}
This code simply changes one of the intervals into the new one, and then erases the other. The max and min functions, of course return the max and min, and this handles the case where intervals are fully contained in a previous interval.
I.E. placing [2, 5] in an array that contains [0, 12] already. The min of these two is [0] and the max is [12] so no changes are made.
I took the max of the two indices to edit just to simplify the next deletion step.
Then if our interval connected two old ones into one(the indices of the min and max are different), deletes the one we didn't edit(which will be the first one as I took the second one to edit by using max on the indices). I did this to keep the array in the same order as before instead of deleting the two old ones and adding a new one to the end.
Note any ugliness added beyond the two binary searches is due to the ugliness of C++ and deleting from a vector without doing a linear scan(had to change from using indices to iterators). However, this function does the same thing as described in words above but uses binary search to do it in O(logN)**** time with O(1) space assuming the intervals are sorted as stated in the problem. If not, then use the linear scan given above.
****Note I feel like it is cheating to say this can be done in O(logN) at all as erasing from an array is O(n) and if one uses a linked list then searching is O(n) regardless of sorted order. However, this is still a "faster" O(n) algorithm then the previous one.
void interval(std::vector<std::pair<int, int>> &a, std::pair<int, int> interv) {
std::vector<std::pair<int, int>>::iterator j = a.end(), k = a.end();
int min = std::numeric_limits<int>::max();
int max = std::numeric_limits<int>::min();
int beg = 0;
int end = a.size()-1;
while (end >= beg) {
int mid = beg + (end - beg) / 2;
if (interv.first <= a[mid].second && a[mid].second < min) {
k = a.begin() + mid; // Sets the iterator to point to a[mid]
min = a[mid].second;
end = end - 1;
} else {
beg = mid + 1;
}
}
beg = 0;
end = a.size()-1;
while (end >= beg) {
int mid = beg + (end - beg) / 2;
if (interv.second >= a[mid].first && a[mid].first > max) {
j = a.begin() + mid; // Sets the iterator to point to a[mid]
max = a[mid].first;
beg = beg + 1;
} else {
end = mid - 1;
}
}
if (j == a.end() || k == a.end()) {
a.push_back(interv);
return;
}
j->first = std::min(k->first, interv.first);
j->second = std::max(j->second, interv.second);
if (k != j) {
a.erase(k);
}
}
Assuming that the interval collection already coming in contains no overlaps and is sorted, then this algorithm is very simple and can be done in O(n) complexity with O(1) memory. Disassembles the old LinkedList and creates a new one:
public static LinkedList<int[]> insert(LinkedList<int[]> intervals, int[] newInterval){
if(intervals == null || newInterval == null){
throw new NullPointerException();
}
LinkedList<int[]> results = new LinkedList<int[]>();
while(!intervals.isEmpty()){
int[] oldInterval = intervals.removeFirst();
//new interval starts before the old interval
if( newInterval[0] < oldInterval[0] ){
//new interval is completely before this old one
if(newInterval[1] < oldInterval[0]){
results.add(newInterval);
results.add(oldIntervall);
while(!intervals.isEmpty()){
results.add(intervals.removeFirst());
}
return results;
}
//new interval starts before and overlaps old interval
else if(newInterval[1] < oldInterval[1]){
newInterval[1] = olderInterval[1];
results.add(newInterval);
while(!intervals.isEmpty()){
results.add(intervals.removeFirst());
}
return results;
}
//otherwise new interval entirely contains old interval. Do nothing
}
//now know new interval starts after old interval
//newInterval overlaps the end of the old interval
else if(newInterval[0] < oldInterval[1]){
//new Interval within old interval
if(newInterval[1] < oldInterval[1]){
results.add(oldInterval);
while(!intervals.isEmpty()){
results.add(intervals.removeFirst());
}
return results;
}
//new interval extends past old interval
else{
newInterval[0] = oldInterval[0];
}
}
//new interval is after old interval
else{
results.add(oldInterval);
}
}
return results;
}
The above code is perfect, except of one small issue.
In the last else, you need to check if the intervals is empty and add the new interval to the list. This is because if the new interval is completely after the end of the old intervals it will be ignored. Say, in this example if the new interval provided is [11,12], it will not be added to the list.
else{
results.add(oldInterval);
if (intervals.isEmpty())
results.add(newInterval);
}
public class IntervalCollection {
int lowesrtLowerBound;//Stores the lowest lower bould in collection
int highestUpperBound;//Stores highest upper bound in collection.
List<Interval> intervalList = new ArrayList<Interval>();
public void insertInterval(int lowerBound, int upperBound) {
if (lowerBound >= upperBound) {
System.out.println("Invalid input");
return;
}
Interval interval = new Interval(lowerBound, upperBound);
if (intervalList.size() == 0) {
System.out.println("Base case");
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
if (lowerBound <= lowesrtLowerBound && upperBound >= highestUpperBound) {
System.out.println("Interval that covers all other intervals in the list");
intervalList.clear();
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
Interval mergeCandidate1 = null;
Interval mergeCandidate2 = null;
for (Interval in : intervalList) {
if (in.equals(interval))
return;//Duplicate
if (mergeCandidate1 == null && in.lowerBound <= lowerBound) {
mergeCandidate1 = in;
}
if (mergeCandidate2 == null && in.upperBound >= upperBound) {
mergeCandidate2 = in;
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
break;
}
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
System.out.println("Merge candidates identified");
Interval i = new Interval(mergeCandidate1.lowerBound, mergeCandidate2.upperBound);
intervalList.add(i);
updateLowestAndHighest(i.lowerBound, i.upperBound);
intervalList.remove(mergeCandidate1);
intervalList.remove(mergeCandidate2);
} else {
System.out.println("Adding a new item");
intervalList.add(interval);
}
}
private void updateLowestAndHighest(int lowerBound, int upperBound) {
if (lowerBound < lowesrtLowerBound) {
lowesrtLowerBound = lowerBound;
}
if (upperBound > highestUpperBound) {
highestUpperBound = upperBound;
}
}
public class IntervalCollection {
int lowesrtLowerBound;//Stores the lowest lower bould in collection
int highestUpperBound;//Stores highest upper bound in collection.
List<Interval> intervalList = new ArrayList<Interval>();
public void insertInterval(int lowerBound, int upperBound) {
if (lowerBound >= upperBound) {
System.out.println("Invalid input");
return;
}
Interval interval = new Interval(lowerBound, upperBound);
if (intervalList.size() == 0) {
System.out.println("Base case");
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
if (lowerBound <= lowesrtLowerBound && upperBound >= highestUpperBound) {
System.out.println("Interval that covers all other intervals in the list");
intervalList.clear();
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
Interval mergeCandidate1 = null;
Interval mergeCandidate2 = null;
for (Interval in : intervalList) {
if (in.equals(interval))
return;//Duplicate
if (mergeCandidate1 == null && in.lowerBound <= lowerBound) {
mergeCandidate1 = in;
}
if (mergeCandidate2 == null && in.upperBound >= upperBound) {
mergeCandidate2 = in;
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
break;
}
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
System.out.println("Merge candidates identified");
Interval i = new Interval(mergeCandidate1.lowerBound, mergeCandidate2.upperBound);
intervalList.add(i);
updateLowestAndHighest(i.lowerBound, i.upperBound);
intervalList.remove(mergeCandidate1);
intervalList.remove(mergeCandidate2);
} else {
System.out.println("Adding a new item");
intervalList.add(interval);
}
}
private void updateLowestAndHighest(int lowerBound, int upperBound) {
if (lowerBound < lowesrtLowerBound) {
lowesrtLowerBound = lowerBound;
}
if (upperBound > highestUpperBound) {
highestUpperBound = upperBound;
}
}
Interval:
public class Interval implements Comparable<Interval> {//Implemented Comparable just in case if we want to Sort the collection.
int lowerBound;
int upperBound;
public Interval(int lowerBound, int upperBound) {
this.lowerBound = lowerBound;;
this.upperBound = upperBound;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("[ ");
builder.append(lowerBound).append(", ").append(upperBound).append(" ]");
return builder.toString();
}
@Override
public boolean equals(Object object) {
if (object == null)
return false;
if (this == object)
return true;
if (!(object instanceof Interval)) {
return false;
}
Interval receivedInterVal = (Interval) object;
return this.lowerBound == receivedInterVal.lowerBound && this.upperBound == receivedInterVal.upperBound;
}
@Override
public int hashCode() {
return super.hashCode() + upperBound + lowerBound;
}
@Override
public int compareTo(Interval that) {
final int BEFORE = -1;
final int EQUAL = 0;
final int AFTER = 1;
if (this == that)
return EQUAL;
if (this.lowerBound == that.lowerBound && this.upperBound == that.upperBound) {
return EQUAL;
}
if (this.lowerBound < that.lowerBound) {
return BEFORE;
}
return AFTER;
}
}
Collection class
public class IntervalCollection {
int lowesrtLowerBound;//Stores the lowest lower bound in collection
int highestUpperBound;//Stores highest upper bound in collection.
List<Interval> intervalList = new ArrayList<Interval>();
public void insertInterval(int lowerBound, int upperBound) {
if (lowerBound >= upperBound) {
System.out.println("Invalid input");
return;
}
Interval interval = new Interval(lowerBound, upperBound);
if (intervalList.size() == 0) {
System.out.println("Base case");
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
if (lowerBound <= lowesrtLowerBound && upperBound >= highestUpperBound) {
System.out.println("Interval that covers all other intervals in the list");
intervalList.clear();
intervalList.add(interval);
updateLowestAndHighest(lowerBound, upperBound);
return;
}
Interval mergeCandidate1 = null;
Interval mergeCandidate2 = null;
for (Interval in : intervalList) {
if (in.equals(interval))
return;//Duplicate
if (mergeCandidate1 == null && in.lowerBound <= lowerBound) {
mergeCandidate1 = in;
}
if (mergeCandidate2 == null && in.upperBound >= upperBound) {
mergeCandidate2 = in;
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
break;
}
}
if (mergeCandidate1 != null && mergeCandidate2 != null) {
System.out.println("Merge candidates identified");
Interval i = new Interval(mergeCandidate1.lowerBound, mergeCandidate2.upperBound);
intervalList.add(i);
updateLowestAndHighest(i.lowerBound, i.upperBound);
intervalList.remove(mergeCandidate1);
intervalList.remove(mergeCandidate2);
} else {
System.out.println("Adding a new item");
intervalList.add(interval);
}
}
private void updateLowestAndHighest(int lowerBound, int upperBound) {
if (lowerBound < lowesrtLowerBound) {
lowesrtLowerBound = lowerBound;
}
if (upperBound > highestUpperBound) {
highestUpperBound = upperBound;
}
}
public void print() {
Collections.sort(intervalList);//Optional:Sorting just to see the intervals in order.
for (Interval in : intervalList) {
System.out.println(in);
}
System.out.println("\n");
}
}
Test:
public class Test {
public static void main(String[] args) {
IntervalCollection intervalCollection = new IntervalCollection();
intervalCollection.insertInterval(-10, -1);
intervalCollection.print();
intervalCollection.insertInterval(0, 2);
intervalCollection.print();
intervalCollection.insertInterval(4, 10);
intervalCollection.print();
intervalCollection.insertInterval(4, 10);
intervalCollection.print();
intervalCollection.insertInterval(-4, 1);
intervalCollection.print();
intervalCollection.insertInterval(-11, 11);
intervalCollection.print();
}
}
public static Collection<Interval> insertAndMergeInterval(Collection<Interval> intervals, Interval toInsert) {
if (toInsert == null) {
throw new IllegalArgumentException();
}
if (intervals == null) {
return Arrays.asList(toInsert);
}
Stack<Interval> result = new Stack<Interval>();
Iterator<Interval> iterator = intervals.iterator();
while (iterator.hasNext()) {
Interval current = iterator.next();
Interval last = result.isEmpty() ? null : result.peek();
if (toInsert != null && toInsert.isBefore(current)) {
if (toInsert.isOverlap(last)) {
last = mergeWithLastInterval(toInsert, result);
} else {
result.push(toInsert);
}
toInsert = null;
}
if (current.isOverlap(last)) {
mergeWithLastInterval(current, result);
} else {
result.push(current);
}
}
if (toInsert != null) {
Interval last = result.isEmpty() ? null : result.peek();
if (toInsert.isOverlap(last)) {
mergeWithLastInterval(toInsert, result);
} else {
result.push(toInsert);
}
}
return result;
}
private static Interval mergeWithLastInterval(Interval current, Stack<Interval> result) {
Interval last = result.pop();
Interval merged = current.merge(last);
return result.push(merged);
}
public static class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public boolean isOverlap(Interval other) {
return (other != null && this.start >= other.start && this.start - 1 <= other.end);
}
public Interval merge(Interval other) {
int start = this.start > other.start ? other.start : this.start;
int end = this.end > other.end ? this.end : other.end;
return new Interval(start, end);
}
public boolean isBefore(Interval other) {
return this.start < other.start;
}
public String toString() {
return "[" + start + ", " + end + "]";
}
}
Here is the C++ solution of problem.
Assumption of this algorithm is that neither of input intervals and out intervals are sorted.
If I can return the output without sorting. The following algorithm can run in O(N) time.
If output should be sorted, it would take O(N log N) due to the sorting steps.
#include<iostream>
#include<list>
using namespace std;
struct itval {
int start;
int end;
itval(int s, int e):start(s), end(e){}
};
list<itval> merge_intervals(itval* input, int len, itval target)
{
list<itval> result;
int start = target.start;
int end = target.end;
for (int i = 0; i <len; i++)
{
if (end >= input[i].start)
{
start = (start < input[i].start)? start: input[i].start;
end = (end > input[i].end)? end: input[i].end;
} else {
result.push_back(input[i]);
}
}
result.push_back(itval(start, end));
return result;
}
public class RangeConsolidator
{
static class Range implements Comparable<Range>
{
int start;
int end;
Range(int s, int e)
{
start = s;
end = e;
}
@Override
public int compareTo(Range o)
{
return start - o.start;
}
@Override
public String toString()
{
return "("+ start +","+ end+ ")";
}
}
/**
* @param args
*/
public static void main(String[] args)
{
TreeSet<Range> input = new TreeSet<Range>(Arrays.asList(new Range[] {
new Range(-10, -1), new Range(0, 2), new Range(4, 10) }));
System.out.println("INPUT:"+ input);
// New item to be inserted
Range newItem = new Range(-5, 1);
System.out.println("Inserting :"+ newItem);
// insert first , and then try to merge
input.add(newItem);
SortedSet<Range> headSet = input.headSet(newItem, false);
SortedSet<Range> tailSet = input.tailSet(newItem, false);
for (Iterator<Range> iterator = headSet.iterator(); iterator.hasNext();)
{
Range r = (Range) iterator.next();
if (r.end > newItem.start)
{
newItem.start = Math.min(r.start, newItem.start);
iterator.remove();
}
}
for (Iterator<Range> iterator = tailSet.iterator(); iterator.hasNext();)
{
Range r = (Range) iterator.next();
if (r.start < newItem.end)
{
newItem.end = Math.max(r.end, newItem.end);
iterator.remove();
}
}
// Merge the consolidated ranges
SortedSet<Range> output = new TreeSet<Range>(headSet);
output.add(newItem);
output.addAll(tailSet);
System.out.println("OUTPUT:"+ output);
}
}
public class RangeConsolidator
{
static class Range implements Comparable<Range>
{
int start;
int end;
Range(int s, int e)
{
start = s;
end = e;
}
@Override
public int compareTo(Range o)
{
return start - o.start;
}
@Override
public String toString()
{
return "("+ start +","+ end+ ")";
}
}
/**
* @param args
*/
public static void main(String[] args)
{
TreeSet<Range> input = new TreeSet<Range>(Arrays.asList(new Range[] {
new Range(-10, -1), new Range(0, 2), new Range(4, 10) }));
System.out.println("INPUT:"+ input);
// New item to be inserted
Range newItem = new Range(-5, 1);
System.out.println("Inserting :"+ newItem);
// insert first , and then try to merge
input.add(newItem);
SortedSet<Range> headSet = input.headSet(newItem, false);
SortedSet<Range> tailSet = input.tailSet(newItem, false);
for (Iterator<Range> iterator = headSet.iterator(); iterator.hasNext();)
{
Range r = (Range) iterator.next();
if (r.end > newItem.start)
{
newItem.start = Math.min(r.start, newItem.start);
iterator.remove();
}
}
for (Iterator<Range> iterator = tailSet.iterator(); iterator.hasNext();)
{
Range r = (Range) iterator.next();
if (r.start < newItem.end)
{
newItem.end = Math.max(r.end, newItem.end);
iterator.remove();
}
}
// Merge the consolidated ranges
SortedSet<Range> output = new TreeSet<Range>(headSet);
output.add(newItem);
output.addAll(tailSet);
System.out.println("OUTPUT:"+ output);
}
}
class Interval(object):
def __init__(self, s=0, e=0):
self.start = s
self.end = e
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
ans = []
intervals.append(newInterval)
if len(intervals) ==1:
return intervals
intervals.sort(key=lambda x:x.start)
prev = pre_start=pre_end = None
for curr in intervals:
if prev:
if curr.start<=pre_end:
pre_end = max(curr.end,pre_end)
else:
ans.append([pre_start,pre_end])
pre_start=curr.start
pre_end = curr.end
else:
pre_start = curr.start
pre_end = curr.end
prev = curr
ans.append([pre_start,pre_end])
return ans
* Since both the lists are listed
* * loop through until one of the list is empty
* * compare both the element
* if equal -> add the element to both union and intersection list
* if not -> add the lesser element to union and increment the index
* * at the end add all the remaining element to the union list
* Time : log(n)
public class UnionAndIntersection {
static List<Integer> aList = Arrays.asList(3, 5, 6, 8, 12, 15 );
static List<Integer> bList = Arrays.asList(2, 4, 5, 8, 10);
public static void main(String[] args) {
int ai=0, bi=0;
List<Integer> union = new ArrayList<>(), intersection = new ArrayList<>();
while(ai < aList.size() && bi < bList.size()) {
if (aList.get(ai) == bList.get(bi)) {
intersection.add(aList.get(ai++));
union.add(bList.get(bi++));
} else if(aList.get(ai) < bList.get(bi)){
union.add(aList.get(ai++));
} else {
union.add(bList.get(bi++));
}
}
if(ai < aList.size()) {
union.addAll(aList.subList(ai, aList.size()));
}else if (bi < aList.size()) {
union.addAll(bList.subList(bi, bList.size()));
}
System.out.println("Union");
union.stream().forEach(System.out::print);
System.out.println("Intersection");
intersection.stream().forEach(System.out::print);
}
public class MergeInterval {
public static class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public boolean isValid() {
return start <=end;
}
}
public static List<Interval> mergeOverlappingInterval(List<Interval> intervals, Interval newInterval) {
if(intervals == null || intervals.size() == 0) {
throw new IllegalArgumentException("Invalid input !!");
}
Collections.sort(intervals, new IntervalComparator());
int newStart = newInterval.start;
int newEnd = newInterval.end;
int curr_start, curr_end = intervals.get(0).end;
if(newStart <= curr_end) {
intervals.get(0).end = Math.max(curr_end, newEnd);
curr_end = intervals.get(0).end;
}
int index = 1;
int prev_end;
while(index < intervals.size()) {
prev_end = curr_end;
curr_start = intervals.get(index).start;
curr_end = intervals.get(index).end;
if(newStart <= curr_end) {
intervals.get(index).end = Math.max(curr_end, newEnd);
}
if(curr_start < prev_end) {
intervals.get(index-1).end = Math.max(prev_end, curr_end);
curr_end = intervals.get(index-1).end;
intervals.remove(index);
} else
index ++;
}
return intervals;
}
private static class IntervalComparator implements Comparator<Interval> {
public int compare(Interval ob1, Interval ob2){
return ob1.start - ob2.start;
}
}
public static void main(String args[]) {
List<Interval> list = new ArrayList<Interval>();
Interval ob1 = new Interval(-10,-1);
Interval ob2 = new Interval(0,2);
Interval ob3 = new Interval(4,10);
list.add(ob1);
list.add(ob2);
list.add(ob3);
List<Interval> result = mergeOverlappingInterval(list, new Interval(-5,1));
for(Interval interval: result) {
System.out.println(interval.start+" "+interval.end);
}
}
}
def overlap(list1):
intervals = [[-10, -1], [0,2], [4,10] ]
if len(list1) == 2:
list1.sort()
intervals.append(list1)
#sort the individual interval and then sort all interval.
new_interval = sorted(intervals, key=lambda t:(t.sort(),t[0]))
print new_interval
#now merge intervals
index = 0
while index < len(new_interval)-1:
if new_interval[index+1][0] <= new_interval[index][1] and new_interval[index][1] >= new_interval[index+1][1]:
new_interval.remove(new_interval[index+1])
elif new_interval[index+1][0] <= new_interval[index][1] or (new_interval[index+1][0]-new_interval[index][1] == 1):
new_interval[index][1] = new_interval[index+1][1]
new_interval.remove(new_interval[index+1])
else:
index+=1
return new_interval
print overlap([-5,1])
def overlap(list1):
intervals = [[-10, -1], [0,2], [4,10] ]
if len(list1) == 2:
list1.sort()
intervals.append(list1)
#sort the individual interval and then sort all interval.
new_interval = sorted(intervals, key=lambda t:(t.sort(),t[0]))
print new_interval
#now merge intervals
index = 0
while index < len(new_interval)-1:
if new_interval[index+1][0] <= new_interval[index][1] and new_interval[index][1] >= new_interval[index+1][1]:
new_interval.remove(new_interval[index+1])
elif new_interval[index+1][0] <= new_interval[index][1] or (new_interval[index+1][0]-new_interval[index][1] == 1):
new_interval[index][1] = new_interval[index+1][1]
new_interval.remove(new_interval[index+1])
else:
index+=1
return new_interval
print overlap([-5,1])
def overlap(list1):
intervals = [[-10, -1], [0,2], [4,10] ]
if len(list1) == 2:
list1.sort()
intervals.append(list1)
#sort the individual interval and then sort all interval.
new_interval = sorted(intervals, key=lambda t:(t.sort(),t[0]))
#now merge intervals
index = 0
while index < len(new_interval)-1:
if new_interval[index+1][0] <= new_interval[index][1] and new_interval[index][1] >= new_interval[index+1][1]:
new_interval.remove(new_interval[index+1])
elif new_interval[index+1][0] <= new_interval[index][1] or (new_interval[index+1][0]-new_interval[index][1] == 1):
new_interval[index][1] = new_interval[index+1][1]
new_interval.remove(new_interval[index+1])
else:
index+=1
return new_interval
print overlap([-5,1])
def overlap(list1):
intervals = [[-10, -1], [0,2], [4,10] ]
if len(list1) == 2:
list1.sort()
intervals.append(list1)
#sort the individual interval and then sort all interval.
new_interval = sorted(intervals, key=lambda t:(t.sort(),t[0]))
#now merge intervals
index = 0
while index < len(new_interval)-1:
if new_interval[index+1][0] <= new_interval[index][1] and new_interval[index][1] >= new_interval[index+1][1]:
new_interval.remove(new_interval[index+1])
elif new_interval[index+1][0] <= new_interval[index][1] or (new_interval[index+1][0]-new_interval[index][1] == 1):
new_interval[index][1] = new_interval[index+1][1]
new_interval.remove(new_interval[index+1])
else:
index+=1
return new_interval
print overlap([-5,1])
def overlap(list1):
intervals = [[-10, -1], [0,2], [4,10] ]
if len(list1) == 2:
list1.sort()
intervals.append(list1)
#sort the individual interval and then sort all interval.
new_interval = sorted(intervals, key=lambda t:(t.sort(),t[0]))
#now merge intervals
index = 0
while index < len(new_interval)-1:
if new_interval[index+1][0] <= new_interval[index][1] and new_interval[index][1] >= new_interval[index+1][1]:
new_interval.remove(new_interval[index+1])
elif new_interval[index+1][0] <= new_interval[index][1] or (new_interval[index+1][0]-new_interval[index][1] == 1):
new_interval[index][1] = new_interval[index+1][1]
new_interval.remove(new_interval[index+1])
else:
index+=1
return new_interval
print overlap([-5,1])
Here's my code submission from leetcode,
/**
* 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 Solution {
public:
// Maintain two pointers current and next, the 'next' pointer increments every loop
// Start with current = 0, next = 1 and for each element until next < size
// if 'next' lies within range then merge the 'next' with 'current' and clear the 'next' element
// else increment 'current' and swap 'current' with 'next' element this way, empty elements are moved to the end.
vector<Interval> merge(vector<Interval>& intervals) {
if (intervals.empty())
return intervals;
auto CompareIntervals = [](const Interval& lhs, const Interval& rhs){ return lhs.start < rhs.start;};
std::sort(intervals.begin(), intervals.end(), CompareIntervals);
int current = 0, next = 1;
for (; next < intervals.size(); ++next) {
if (intervals[next].start <= intervals[current].end) { // merge with current
intervals[current].end = std::max(intervals[next].end, intervals[current].end);
intervals[next] = Interval(); // clear the merged element
}
else {
if (++current != next)
std::swap(intervals[current], intervals[next]);
}
}
if (current != next) // if elements were removed
intervals.resize(current+1);
return intervals;
}
};
#include <iostream>
#include <vector>
#include <cmath>
#include <list>
using namespace std;
void interval(list<pair<int, int>> &I, pair<int, int> m) {
bool f = false;
list<pair<int, int>>::iterator it = I.begin();
while(it!= I.end())
{
if(m.second<(*it).first) {
I.insert(it, m); return;
} else if(m.first>(*it).second) {
++it; continue;
} else {
(*it).first = min((*it).first, m.first);
(*it).second = max((*it).second, m.second);
f = true; break;
}
}
if(f == false || it == I.end()) {
I.push_back(m); return;
}
list<pair<int, int>>::iterator it2 = it; ++it;
while(it!=I.end()) {
if((*it).first <= (*it2).second) {
(*it2).second = max((*it2).second, (*it).second);
it = I.erase(it);
} else {
return;
}
}
}
int main() {
std::list<std::pair<int, int>> a = {
std::pair<int, int>(-10, -1), std::pair<int, int>(0, 2), std::pair<int, int>(4, 10), std::pair<int, int>(14, 19), };
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\n Adding [-5,1]:\n";
interval(a, std::pair<int, int>(-5, 1));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [3,9]:\n";
interval(a, std::pair<int, int>(3, 9));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [1,3]:\n";
interval(a, std::pair<int, int>(1, 3));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-15,13]:\n";
interval(a, std::pair<int, int>(-15, 13));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [-3,21]:\n";
interval(a, std::pair<int, int>(-3, 21));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << "\nAdding [30, 50]:\n";
interval(a, std::pair<int, int>(30, 50));
for (auto i : a) {
std::cout << "[" << i.first << ", " << i.second << "] ";
}
std::cout << std::endl;
return 0;
}
Thanks to psycophantEve for test cases and driver program. Below is stdout
[-10, -1] [0, 2] [4, 10] [14, 19]
Adding [-5,1]:
[-10, 2] [4, 10] [14, 19]
Adding [3,9]:
[-10, 2] [3, 10] [14, 19]
Adding [1,3]:
[-10, 10] [14, 19]
Adding [-15,13]:
[-15, 13] [14, 19]
Adding [-3,21]:
[-15, 21]
Adding [30, 50]:
[-15, 21] [30, 50]
public class IntervalTreeAlternate {
TreeSet<Interval> intervals = new TreeSet<>();
public void addInterval(Interval interval) {
intervals.add(interval);
}
//variation of above
public boolean isOverlapping(int low1, int high1, int low2, int high2) {
return low1 <= high2 && low2 <= high1;
}
//returns all overlaps
public ArrayList<List<Interval>> findAllOverlappingIntervals() {
ArrayList<List<Interval>> overlaps = new ArrayList<>();
Iterator<Interval> iterator = intervals.iterator();
try {
Interval min = intervals.first();
Interval successor = intervals.higher(min);
while (successor != null && min != null) {
//create a list for each set of overlapping intervals
List<Interval> overlap = new LinkedList<>();
overlap.add(min);
while (successor != null && isOverlapping(min.low, min.high, successor.low, successor.high)) {
//add the successor to the overlap list
overlap.add(successor);
//the min is now the successor
min = successor;
//check the next successor (for overlaps)
successor = intervals.higher(successor);
}
if (overlap.size() > 0) {
overlaps.add(overlap);
}
//is out of the loop either because there was no overlap or because
min = successor;
successor = intervals.higher(min);
}
} catch (NoSuchElementException ex) {
//in practice we would do something special here...
} catch (NullPointerException ex1) {
//in practice we would do something special here...
}
return overlaps;
}
public void mergeOverlaps() {
ArrayList<List<Interval>> overlaps = findAllOverlappingIntervals();
for (List<Interval> l : overlaps) {
if (l.size() > 1)
mergeOverlaps(l);
}
}
private void mergeOverlaps(List<Interval> overlaps) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < overlaps.size(); i++) {
if (min > overlaps.get(i).low)
min = overlaps.get(i).low;
if (max < overlaps.get(i).high)
max = overlaps.get(i).high;
//remove this element from the interval tree
intervals.remove(overlaps.get(i));
}
//add the merged interval
intervals.add(new Interval(min, max));
}
}
I think this can be done with the help of a sorted list (a list of pair of integers for each interval), sorting done according to the first element of each pair.
- Rohit June 17, 2015Whenever there is a request for inserting an interval do a binary search to find the first pair such that the first integer of the pair is just smaller than the given pairs first element.
Now if the second integer of this found pair is larger than the first integer of given pair then
check if the second integer of the given pair is smaller than the second integer of the just found pair, if yes then no need to make any changes else check if the second integer of the given pair is smaller than the first element of the pair after the just found pair in the list, if yes then increase the length of the just found interval otherwise merge the found pair with the next pair.
Handle those cases where we do not find any pair in list, by either appending the given pair in front of list or at the end of the list.