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