Merge Overlapping Interval

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

Below code uses 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
		DataNode2LinkedList2 linkedList = new DataNode2LinkedList2();
		//O(n log n) operation
		for(int[] data:originalIntervals){
			linkedList.insert(new DataNode2(data));
		}

		System.out.println("---------Sorted?merged Intervals----------");
		int[][] sortedIntervals = linkedList.traverse();

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

	}

}

/**
 * @author Ashwin Rayaprolu
 *
 */
class DataNode2LinkedList2 {
	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;
	}

}

Below Code Uses 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
		MergeBinaryInsertIntervalDataNode linkedList = new MergeBinaryInsertIntervalDataNode();
		//O(n log n) operation
		for(int[] data:originalIntervals){
			linkedList.insert(linkedList.rootNode,data);
		}
		
		
		System.out.println("---------Sorted?merged Intervals----------");
		linkedList.traverse(linkedList.rootNode);

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

}