CareerCup

It is 1d interval search problem.
Algorithm:
Create BST where each node stores an interval (lo,hi).
Use left endpoint as BST key. (here lo is BST key)
Store max endpoint in subtree rooted at node. (consider hi of all nodes)
Now:
To search for any one interval that intersects query interval (lo,hi):
If interval in node intersects query interval, return it.
Else if left subtree is null, go right.
Else if max endpoint in left subtree is less than lo, go right.
Else go left.

Sort the ranges and remove one of the ranges that are overlapping. Time complexity O(nlogn), written in C++.

Output:

(1, 2) (3, 6) (8, 10)

Code:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

struct range {
	range(int a, int b) : a_(a), b_(b) { }
	
	bool operator<(const range& other) const {
		return a_ < other.a_ || b_ < other.b_;
	}
	
	int a_;
	int b_;
};

std::ostream& operator<<(std::ostream& os, const range& r) {
	os << "(" << r.a_ << ", " << r.b_ << ")";
	return os;
}

bool overlaps(const range& r1, const range& r2) {
	return (r2.a_ <= r1.b_) || (r2.a_ == r1.b_ && r2.b_ >= r1.b_);
}

std::vector<range> find_non_overlap(std::vector<range>& ranges) {
	// Sort the ranges. Uses operator< from range struct. O(nlogn)
	std::sort(ranges.begin(), ranges.end());

	// Remove ranges that are overlapping. O(n)
	for (auto it = std::next(ranges.begin()); it != ranges.end(); it++) {
		auto prev_it = std::prev(it);
		if (overlaps(*prev_it, *it)) {
			it = ranges.erase(prev_it);
		}
	}

	return ranges;
}

/**
 * Given a list of ranges as input ((1,2),(3,4),(3,6),(8,10)), the output would
 * be those ranges that don't overlap. For example, the output could be merging
 * the ranges 1) (1,2) (3,4) 2) (1,2) (3,6) etc.
 * 
 * The output cannot contain (3,4),(3,6) as 3 is common to both.
 */
int main() {
	std::vector<range> ranges{{1,2}, {3,4}, {3,6}, {8,10}};
	std::vector<range> result = find_non_overlap(ranges);
	std::copy(result.begin(), result.end(), std::ostream_iterator<range>(std::cout, " "));
}

1) Sort pairs by lower range (nlogn)
2) Go through list of pairs checking overlap (merge node) and duplicate (remove node)

here my version:

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<pair<int,int>> get_pairs_non_overlapping(vector<pair<int,int>> &vec) {
	unordered_map<int,vector<int>> ht;
	set<int, std::greater<int>> to_del_pairs;
	
	for(int i = 0; i < vec.size(); i++) {
		int start = vec[i].first;
		int end = vec[i].first + (vec[i].second - vec[i].first);
		
		for(int j = start; j <= end; j++) {
			auto it = ht.find(j);
			
			if(it == ht.end()) {
				vector<int> vec;
				vec.push_back(i);
				
				ht.insert(make_pair(j, vec));
			}
			else {
				it->second.push_back(i);
			}
		}
	}
	
	for(auto it = ht.begin(); it != ht.end(); it++) {
		if(it->second.size() > 1) {
			for(auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
				to_del_pairs.insert(*it2);
			}
		}
	}
	
	for(auto it = to_del_pairs.begin(); it != to_del_pairs.end(); it++) {
		vec.erase(vec.begin() + *it);	
	}
	
	return vec;
}

int main() {
	// your code goes here
	
	vector<pair<int,int>> in = {{1,2}, {3,4}, {3,6}, {8,10}};
	
	vector<pair<int,int>> out = get_pairs_non_overlapping(in);
	
	for_each(out.begin(), out.end(), [](pair<int,int> p) { cout << p.first << ", " << p.second << endl; });
	
	return 0;
}

Brut force:

the function:

public List findNonOverLapingPair(List<int[]> set) {

		List<int[]> temp = new ArrayList<int[]>(set);
		List temp2 = new ArrayList();
		
		for (int i = 0; i < set.size(); i++) {
			temp.remove(0);
			int check[] = set.get(i);
			for (int[] is : temp) {
				if (((check[0] < is[0] && check[0] < is[1]) && (check[1] < is[0] && check[1] < is[1]))
						|| ((check[0] > is[0] && check[0] > is[1]) && (check[1] > is[0] && check[1] > is[1]))) {

					Object o[]= {check,is};
					temp2.add(o);
				}
			}
		}
		return temp2;
	}

test code:

public static void main(String[] args) {
		List<int[]> set = new ArrayList<int[]>();
		int[] a = { 1, 2 };
		int[] a2 = { 3, 4 };
		int[] a3 = { 3, 6 };
		int[] a4 = { 8, 10 };
		set.add(a);
		set.add(a2);
		set.add(a3);
		set.add(a4);
		List l=new Main().findNonOverLapingPair(set);
		for(Object o:l){
			Object[] b=(Object[])o;
			int[] i=(int[]) b[0];
			int[] j=(int[]) b[1];
			System.out.println(i[0]+","+i[1]+"::"+j[0]+","+j[1]);
		}
	}

output:

1,2::3,4
1,2::3,6
1,2::8,10
3,4::8,10
3,6::8,10

DO we have to ouput always in pairs? For example can answer in example be {(1,2) (3,6) 8,10)}

I have a hard time understanding this question. Are we supposed to print all pairs of ranges that don't overlap? Can someone elaborate and provide more examples? Thanks.

@Sunny:

yes, check if a number within the range overlaps with any other range.

examples:

input: {{1,2}, {3,4}, {3,6}, {8,10}}
output: {{1,2}, {8,10}}
explanation: {3,4}, {3,6} ...overlap and will be removed

input: {{1,2}, {3,5}, {4,6}, {8,10}}
output: {{1,2}, {8,10}}
explanation: {3,5}, {4,6} ...overlap and will be removed

input: {{1,6}, {3,4}, {5,7}, {8,10}}
output: {{8,10}}
explanation: {1,6}, {3,4}, {5,7} ...overlap and will be removed

public void doItNew(int[][] x) {
        int[] checker = new int[x.length];
        for (int i = 0; i < x.length - 1; i++) {
            for (int j = i + 1; j < x.length; j++) {
                if (checkOverLap(x[i], x[j])) {
                    checker[i] = -1;
                    checker[j] = -1;
                }
            }
        }
        for (int i = 0; i < x.length ; i++) {
            if (checker[i] != -1) {
                for (int a1 : x[i]) {
                    System.out.print(a1 + "\t");
                }
            }
        }
    }

    public boolean checkOverLap(int[] a, int[] b) {
        return a[0] - b[1] <= 0 && a[1] - b[0] >= 0;
    }

Its a very easy question of "Activity selection problem", an application of greedy algorithm.

If we assume that the input array comes already sorted (in the problem statement it comes sorted), just traverse this array and eliminate the overlapping pairs, then it has an O(n) for both time and space complexities.

Jumping directly to code without understanding the problem is just stupid. What to return if the array contains (1,2) (3,4) (1,2,3,4,5)? (1,2) + (3,4) or (1,2,3,4,5)? Is it asking for the largest coverage?

Create 2 separate sets of tuples, in one set sort the intervals by the first number, in the second set sort the intervals by the second number. For each tuple in the first set, use binary search to find all tuples in the second set for which the second number in the tuple from the second set is less than equal to the first number in the tuple from the first set.

Sorting takes O(nlogn) time. Forming the set of intervals for each of n tuple takes O(logn) time (binary search). Thus O(nlogn) time complexity and O(n) space complexity.

This problem is like interval scheduling problem in which we have to schedule jobs which are compatible. We are given here (start,finish) time pair of each job.

Two approach:

Greedy:
1) Sort them based on the range end of each (start,end) pair.
2) Now take first pair which end first and add it to solution.
3) Iterate on sorted job to find jobs which are compatible with the result. This will be one scan to the input.
Note: We are adding job greedily to the solution set.

DP:
Sort the based on the end range.
Create Array which account for last job compatible with jth jon. Let it be p(j).
Now Use this recurrence solution.
M[i] = max(1+p(i),M[i-1]).

M[n] will give you number of max set compatible.
For printing solution you can iterate over M array one scan.

public class MergingRang {
	public static void main(String[] args) {
		List<Point> pointList = new ArrayList<Point>();
		Point point;		
		point = new Point(3,4);
		pointList.add(point);
		point = new Point(1,2);
		pointList.add(point);
		point = new Point(3,6);
		pointList.add(point);
		point = new Point(8,10);
		pointList.add(point);
		Collections.sort(pointList);
		for(int i=0;i<pointList.size()-1;i++){
			for(int j=pointList.size()-1;j>i;j--){								
				if((pointList.get(i).y>=pointList.get(j).x) || (pointList.get(i).y>=pointList.get(j).y))
					break;
				else
					System.out.println("("+pointList.get(i).x+","+pointList.get(i).y+")"+
							"("+pointList.get(j).x+","+pointList.get(j).y+")");
			}
		}
		
	}

}
class Point implements Comparable<Point>{
	int x;
	int y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public int compareTo(Point o) {
		// TODO Auto-generated method stub
		return x-o.x;
	}
}

package org.ram.java.exercises.careercup;

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.LinkedList;

public class RangeProblem {
	public static void main(String args[]) {

		String pair1 = "1,2";
		String pair2 = "3,6";
		String pair3 = "2,3";
		ArrayList<String> al = new ArrayList<String>();
		LinkedHashSet<Integer> ls = new LinkedHashSet<>();
		al.add(pair1);
		al.add(pair2);
		al.add(pair3);
		for (String st : al) {
			LinkedList<Integer> li = new LinkedList<Integer>();
			Boolean canadd = true;
			String ar[] = st.split(",");
			Integer val = Integer.parseInt(ar[0]);
			for (int i = 0; i <= Integer.parseInt(ar[1])
					- Integer.parseInt(ar[0]); i++) {
				System.out.println(val);
				li.add(val);
				val++;

				if (ls.contains(val)) {
					canadd = false;
				} else {
					ls.add(val);
				}
			}
			if (canadd) {
				System.out.println(li);
			}
		}

	}

}

/*
 * Given a list of ranges as input ((1,2),(3,4),(3,6),(8,10))
 * the output would be those ranges that don't overlap.
 * For example, the output could be merging the ranges 
 * 1) (1,2),(3,4) 
 * 2) (1,2) (3,6) etc
 * 
 * The output cannot contain (3,4),(3,6) as 3 is common to both.
 */
package sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;


public class MergeOverLappingIntervals
{

	public static class Interval implements Comparable<Interval>
	{
		int start = 0;
		int end = 0;
		public Interval(int start, int end)
		{
			this.start = start;
			this.end = end;
		}
		
		public Interval mergeWith(Interval other)
		{
			if((this.end >= other.start && this.start <= other.start)
			|| (this.start <= other.end && this.end >= other.end)
			|| (this.start >= other.start && this.end <= other.end)
			|| (this.start <= other.start && this.end >= other.end))
			{
				return new Interval(Math.min(this.start, other.start), Math.max(this.end, other.end));
			}
			else
			{
				return null;
			}
		}
		public int length()
		{
			return this.end - this.start;
		}
		public String toString()
		{
			return "(" + this.start + ", " + this.end + ")";
		}

		@Override
		public int compareTo(Interval other) {
			if(other == null)
			{
				throw new java.lang.IllegalArgumentException("Comparison can not be done with a NULL object!");
			}
			return this.start - other.start;
		}
	}
	
	public static List<Interval> mergeNow(List<Interval> input)
	{
		if(input == null || input.size() < 1)
		{
			return input;
		}
		Collections.sort(input);
		List<Interval> output = new ArrayList<Interval>();
		Iterator<Interval> iterator = input.iterator();
		Interval left = iterator.next();
		Interval right = null;
		while(iterator.hasNext())
		{
			right = iterator.next();
			Interval merged = left.mergeWith(right);
			if(merged != null)
			{
				left = merged;
			}
			else
			{
				output.add(left);
				left = right;
				// add the last one
				if(!iterator.hasNext())
				{
					output.add(right);
				}
			}
		}
		return output;
	}
	
	public static void main(String[] args) {
		List<Interval> input = new ArrayList<Interval>();
		input.add(new Interval(8,10));
		input.add(new Interval(3,4));
		input.add(new Interval(1,2));
		input.add(new Interval(3,6));
		input.add(new Interval(4,5));
		System.out.println(input);
		System.out.println(mergeNow(input));
	}

}