Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Merging Overlapping Intervals [Code Snippet]

### Here are a couple of separate approaches to merging overlapping data intervals. Take a look at both the Double Linked List and Binary Tree approaches.

· Java Zone
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Download Microservices for Java Developers: A hands-on introduction to frameworks and containers. Brought to you in partnership with Red Hat.

I recently came across a problem of merging data with overlapping lower and upperbound data. I tried multiple approaches.

The below code uses the Double Linked List approach:

``````/**
* 1. For the original DataNode2 we need to make sure we merge nodes when ever we see overlap
*
* @author Ashwin Rayaprolu
*
*/
public class MergeInsertIntervals {

/**
* @param args
*/
public static void main(String[] args) {
int[][] originalIntervals = { { 94230, 94299 }, { 94289, 94699 }, { 94200, 94240 }, { 94133, 94133 } };
// Sort our array based on lower bound number
//O(n log n) operation
for(int[] data:originalIntervals){
}

System.out.println("---------Sorted?merged Intervals----------");

System.out.println("---------Merged Intervals----------");
}
}

/**
* @author Ashwin Rayaprolu
*
*/
DataNode2 firstNode;
DataNode2 lastNode;

int size = 0;
// O(log n) operation
void insert(DataNode2 newNode) {
if (firstNode == null) {
firstNode = newNode;
lastNode = newNode;
return;
}

// Keep interval on left if lower bound is < than tempPointer
DataNode2 tempPointer = firstNode;

if (newNode.data[0] < tempPointer.data[0]) {
while (tempPointer.leftPointer != null && newNode.data[0] < tempPointer.data[0]) { tempPointer = tempPointer.leftPointer; }  //If new node is overlapping then merge with current node and return if(newNode.data[1]>=tempPointer.data[0]){
//tempPointer.data[1]=
tempPointer.data[0] = newNode.data[0];
return;
}

newNode.rightPointer = tempPointer;

if (tempPointer.leftPointer == null) {
firstNode = newNode;
}

tempPointer.leftPointer = newNode;
++size;

} else {
while (tempPointer.rightPointer != null && newNode.data[0] >= tempPointer.data[0]) {
tempPointer = tempPointer.rightPointer;
}

//If new node is overlapping then merge with current node and return
if(tempPointer.data[1]>=newNode.data[0]){
//tempPointer.data[1]=
tempPointer.data[1] = newNode.data[1];
return;
}

newNode.leftPointer = tempPointer;

if (tempPointer.rightPointer == null) {
lastNode = newNode;
}

tempPointer.rightPointer = newNode;
++size;
}
}

int[][] traverse() {
DataNode2 tempPointer = firstNode;
int[][] sortedArray = new int[size + 1][2];
int index = 0;
while (tempPointer != null) {
sortedArray[index] = tempPointer.data;
++index;
System.out.println("{" + tempPointer.data[0] + "," + tempPointer.data[1] + "}");
tempPointer = tempPointer.rightPointer;
}
return sortedArray;
}
}

/**
* Data Node used for sorting
*
* @author Ashwin Rayaprolu
*
*/
class DataNode2 {
int[] data = {};
DataNode2 leftPointer;
DataNode2 rightPointer;

public DataNode2(int[] data) {
this.data = data;
}
}

``````

The below code uses the Binary Tree approach:

``````/**
* 1. For the original MergeBinaryInsertDataNode we need to make sure we merge nodes when ever we see overlap
*
* @author Ashwin Rayaprolu
*
*/
public class MergeBinaryInsertInterval {

/**
* @param args
*/
public static void main(String[] args) {
int[][] originalIntervals = { { 94230, 94299 }, { 94289, 94699 }, { 94200, 94240 }, { 94133, 94133 } };
// Sort our array based on lower bound number
//O(n log n) operation
for(int[] data:originalIntervals){
}

System.out.println("---------Sorted?merged Intervals----------");
System.out.println("---------Merged Intervals----------");
}
}

/**
* @author Ashwin Rayaprolu
*
*/
class MergeBinaryInsertIntervalDataNode {
MergeBinaryInsertDataNode rootNode;

int size = 0;

// Inserting or pushing data to binary tree
public void insert(MergeBinaryInsertDataNode currentNode, int[] newData) {
MergeBinaryInsertDataNode tempNode = new MergeBinaryInsertDataNode(newData);
// If first Node then make it root node
if (rootNode == null) {
rootNode = tempNode;
return;
}

// If new node data >= root node data move to right
if (currentNode.data[0] <= tempNode.data[0]) {

//If new node is overlapping then merge with current node and return
if(currentNode.data[1]>=tempNode.data[0]){
//tempPointer.data[1]=
currentNode.data[1] = tempNode.data[1];
return;
}

if (currentNode.rightPointer == null) {
currentNode.rightPointer= tempNode;
} else {
insert(currentNode.rightPointer, newData);
}
} else {
//If new node is overlapping then merge with current node and return
if(tempNode.data[1]>=currentNode.data[0]){
//tempPointer.data[1]=
currentNode.data[0] = tempNode.data[0];
return;
}

if (currentNode.leftPointer == null) {
currentNode.leftPointer = tempNode;
} else {
insert(currentNode.leftPointer, newData);
}
}
}

/**
* @param currentNode
*/
public void traverse(MergeBinaryInsertDataNode currentNode) {
if (currentNode == null) {
return;
}
traverse(currentNode.leftPointer);
System.out.println("{"+currentNode.data[0]+","+currentNode.data[1]+"}");
traverse(currentNode.rightPointer);
}
}

/**
* Data Node used for sorting
*
* @author Ashwin Rayaprolu
*
*/
class MergeBinaryInsertDataNode {
int[] data = {};
MergeBinaryInsertDataNode leftPointer;
MergeBinaryInsertDataNode rightPointer;

public MergeBinaryInsertDataNode(int[] data) {
this.data = data;
}

}

``````

Download Building Reactive Microservices in Java: Asynchronous and Event-Based Application Design. Brought to you in partnership with Red Hat

Topics:
java ,interval ,data management

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of Ashwin Rayaprolu, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.