CareerCup

hi shaik,
is the array given is having ranges in sorted order or not??
unsorted can be {0,3,7,9,1,5,8,13}

package com.test;

import java.util.*;


public class MyOverLapRange {

public static void main (String args[]){

int a []={0,3,1,5,7,9,8,13};

Map<Integer, Integer> b= new HashMap<Integer, Integer>();
List<Integer> finalNonOverLapInerval =new ArrayList<Integer>();

boolean isInterval=true;
//put the integers in pairs
for (int i=0 ;i< a.length;i++)
{
if (i<a.length/2){
if ( i==0){
b.put(a[i], a[i+1]);
}
else{

b.put(a[i+i], a[i+i+1]);
}
}

}


//loop over elements of array to see if occur in any of the interval in this style x<a<y
//if not add them to a non-overlapping intervals
for (int i=0 ;i< a.length;i++){

isInterval=true;

//uncomment to trace values
// System.out.println("a = " + i + ", Value = " + a[i]);

Iterator<Map.Entry<Integer, Integer>> entries = b.entrySet().iterator();


while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();

//uncomment to trace values
// System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());

if ( entry.getKey()< a[i] && a[i]< entry.getValue()){

isInterval=false;
}
}

if (isInterval){

finalNonOverLapInerval.add(a[i]);
}
}

//printing the non-overlapping intervals
for (int i=0 ;i< finalNonOverLapInerval.size();i++){

System.out.println("result["+i+"]: "+finalNonOverLapInerval.get(i));

}
}


}

The ranges are in sorted order, {0,3,1,5,7,9,8,13}

Thanks Rajkumari, it's working perfectly fine, I'm just trying to understand it now.

I can't understand the question. @shaik can you explain a bit more what is being asked?

Maybe I am not understanding the question correctly, but why can you not do something simple like the code I have below. You can simply iterate over the array once, which and get all of the values you need. Basically it will given you the end points of each non-overlapping arrays of a given range.

public class arrayTest {
	public static void main(String args[]) {
		int[] a = {0,3,1,5,7,9,8,13};
		int range = 3;
		for (int i = 0;i<a.length;i++) {
			if ((i%(range+1)==range) || ((i%(range+1)) ==0)) {
				System.out.println(a[i]);
			}
			if (i == (a.length-1) && ((i % (range+1)) != range)) {
				System.out.println(a[i]);
			}
		}
	}
}

can you elaborate what is being asked in the question.

can you explain the question

int b[]={0,3,1,5,7,9,8,13};
	int n=sizeof(b)/sizeof(b[0]);
	for(i=0;i<=n/2;i+=2)
	{
		int j=i+2;
		while(j<n-1)
		{
			if(b[j]>b[i] && b[j]<b[i+1])
				printf("%d\t%d\n",b[i],b[j+1]);
			else
				break;
			j+=2;
		}
	}

void NonOverlappingRanges(int[] arr)
        {
            int min = 0;
            int max = 1;
            for (int i = 2; i < arr.Length; i += 2)
            {
                if (arr[i] < arr[max])
                {
                    if (arr[i + 1] <= arr[max])
                    {
                        arr[i] = -1;
                        arr[i + 1] = -1;
                    }
                    else
                    {
                        arr[max] = arr[i] = -1;
                        max = i + 1;
                    }
                }
                else
                {
                    min = i;
                    max = i + 1;
                }
            }
            for (int i = 0; i < arr.Length; i++)
            {
               if(arr[i]!=-1)
                Console.WriteLine(arr[i]);
            }
        }

import java.util.LinkedList;
import java.util.List;

public class OverLappingRanges {

public static void main(String[] args) {
int inpranges[] = {0,3,1,5,7,9,8,13};
List<Range> listR = new LinkedList<Range>();
for(int i=0;i<inpranges.length/2;i++){
Range r = new Range(inpranges[i*2], inpranges[i*2+1]);
listR.add(r);
}

List<Range> finalRanges = new LinkedList<Range>();
Range prev = listR.get(0);
int i =1;
while(i< listR.size()){
Range curr = listR.get(i);
if(prev.low<= curr.low && prev.high >= curr.low){
prev.high = Math.max(prev.high, curr.high);
}else{
finalRanges.add(prev);
prev = curr;
}
i++;
}
finalRanges.add(prev);

for (Range range : finalRanges) {
System.out.print(range.low+" "+range.high+" ");
}
System.out.println();
}

}

class Range{
int low;
int high;
public Range(int low, int high){
this.low = low;
this.high = high;
}
}

I think A dynamic connectivity (Quick Union) approach would be a best fit for this problem. the union operation would group two ranges if they overlap else not.
The find operation would return the group (root) of the query group.

Scala:

Assuming input in tuple format:

def nonOvrLapping(a: Array[(Int, Int)],r: Array[Int]): Array[Int] = a match {
 case Array() => r
 case Array(x,y,z@_*) if(x._2 > y._1) => nonOvrLapping(z.toArray, (r:+x._1):+y._2)
 case Array(x,y,z@_*) => nonOvrLapping(z.toArray,r)
}

scala> nonOvrLapping(Array((0,3), (1,5), (7,9), (8,13)), Array())

res49: Array[Int] = Array(0, 5, 7, 13)

public class rengetest
{
    public static void main(String[] args)
    {
        int[] A = { 0, 3, 1, 5, 7, 9, 8, 13 };
        for (int i = 1; i < A.length; i += 2)
        {
            int rangeStart = A[i - 1];
            int rangeEnd = A[i];
            for (int l = rangeStart; l <= rangeEnd; l++)
            {
                boolean isInRange = false;
                for (int j = 1; j < A.length; j += 2)
                {
                    int internalRangeStart = A[j - 1];
                    int internalRangeEnd = A[j];
                    isInRange = isInRange(l, internalRangeStart,
                            internalRangeEnd);
                    if (isInRange)
                    {
                        break;
                    }
                }
                if (isInRange == false)
                {
                    System.out.println(l);
                }
            }
        }

    }

    public static boolean isInRange(int number, int rangestart, int rangeEnd)
    {
        if (number > rangestart && number < rangeEnd)
        {
            return true;
        }
        return false;
    }

}

If input is not sorted,sort it with begin time inc

def unionranges(array):
    start = array[0]
    end = array[1]
    result = []
    for i in xrange(2,len(array),2):
        if array[i] > end:
            result.append((start,end))
            start = array[i]
            end = array[i+1]
        else:
            if array[i+1] > end:
                end = array[i+1]
    result.append((start,end))
    return result

import java.util.*;
public class Overlap {

public Overlap() {
// TODO Auto-generated constructor stub
}

public static Set<Integer> fixOverLap(int[]A){

Set<Integer> newList = new LinkedHashSet<Integer>();
int pre=0;
for (int i=1;i<A.length+1;i++)
{
if (i==(A.length))
{

if (A[i-1]>pre)
{
newList.add(A[i-1]);

}
break;
}

if (A[i-1]<=A[i])
{
newList.add(A[i-1]);

pre=A[i-1];

}
else{
i+=1;

}
}
return newList;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int []A={0,3,1,5,7,9,8,13};

System.out.println(fixOverLap(A));

}

}

private int[] NonoverlappingArray(int[] ArrayInput)
{
int[] ArrayOutput = new int(1000); //suppose the entries are <1000
for(int i=1;i<ArrayInput.length()-1;i++)
{
if(ArrayInput[i] > ArrayInput[i-1] && ArrayInput[i] < ArrayInput[i+1])
{
ArrayOutput[i] = ArrayInput[i];
}
else if(ArrayInput[i] < ArrayInput[i-1] && ArrayInput[i] > ArrayInput[i+1])
{
ArrayOutput[i] = ArrayInput[i];
}
}
return ArrayOutput.RemoveNull();
}