merge array range

public class Node implements Comparator
{
    public int value;
    public boolean isStart;

    public Node( int value,  int isStart )
    {
        this.value = value;
        this isStart = isStart;
    }

    public int compare( Object o1 , Object o2 )
    {
        Node comparaee = ( Node ) o1;
        Node comparator = ( Node ) o2;

        return comparaee – comparator;
    }

}

// arr[] = {1,3, 2, 6, 8, 10, 15, 18}
// should be merged as {1, 6, 8, 10, 15, 18}
public int[] mergeArray( int[] arr )
{
    if( arr.length <= 0 )
    {
        return null;
    }

    Node[] nodeArr = new Node[arr.length]();
    Vector<Node> result = new Vector<Node>( );

    // prepare all data
    for( int i = 0; i < arr.length; i++ )
    {
        if( i % 2 == 0 )
        {
            nodeArr[i] = new Node( arr[i], false );
        }
        else
        {
            nodeArr[i] = new Node( arr[i], true );
        }
    }

    Arrray.sort( nodeArr );

    Stack<Node> st = new Stack<Node>();
    for( int i = 0; i < nodeArr.length; i++ )
    {
        // after sorting, put all start points into stack
        if( nodeArr[i].isStart )
        {
            st.push( nodeArr[i] );
        }
        // each time meet a end point, we pop the stack
        else
        {
            Node start = st.pop( );
            //if the stack is empty, we find correct range
            if( st.isEmpty( ) )
            {
                vector.add( start );
                vector.add( nodeArr[i] );
            }
        }
    }
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s