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

Merging Overlapping Intervals [Code Snippet]

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

Try Okta to add social login, MFA, and OpenID Connect support to your Java app in minutes. Create a free developer account today and never build auth again.

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


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

}

Build and launch faster with Okta’s user management API. Register today for the free forever developer edition!

Topics:
java ,interval ,data management

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

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}