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

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

}

Download Modern Java EE Design Patterns: Building Scalable Architecture for Sustainable Enterprise Development.  Brought to you in partnership with Red Hat

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.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}