CareerCup

def findRange(l):
    newL = sorted(l, key = lambda x: (x[0], x[1]))
    print newL
    lower_bound = 0
    upper_bound = 0
    result = 0
    for i in newL:
        if i[0] < upper_bound:
            # find lap here!
            if i[1] < upper_bound:
                continue
            else:
                result += i[1] - upper_bound
        else:
            lower_bound = i[0]
            upper_bound = i[1]
            result += upper_bound - lower_bound
    return result

public static int findRange(ArrayList<Interval> intervals) {
		Collections.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if (o1.start > o2.start) {
					return 1;
				} else if (o1.start > o2.start) {
					return -1;
				} else if (o1.end > o2.end){
					return 1;
				} else if (o1.end > o2.end) {
					return -1;
				} else {
					return 0;
				}
			}
		});
		
		int range = 0;
		int s = 0;
		int i = 0;
		while (i < intervals.size()) {
			int j = i + 1;
			int e = intervals.get(i).end;
			while (j < intervals.size() && e >= intervals.get(j).start) {
				e = Math.max(e, intervals.get(j).end);
				j++;
				
			}
			range += e - intervals.get(s).start;
			i = j;
			s = j;
		}
		return range;
	}

I am using a LinkedHashSet. Everything else takes O(n). Can any of you review this ?

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

public class Intervals{
	
	static int findRange(Interval[] data){
		Set<Integer> res = new LinkedHashSet<Integer>();
		for(int i=0;i<data.length;i++){
			for(int j=data[i].start;j<=data[i].end;j++){
				res.add(j);
			}
		}
		
		Iterator<Integer> it = res.iterator();
		int start = it.next(), last = start, tmp = start, result = 0;
		while(it.hasNext()){
			tmp = it.next();
			if(tmp-last == 1){
				last = tmp;
			}else{
				result += (last-start);
				start = tmp;
				last = start;
			}
		}
		result += (tmp-start);
		return result;
	}
	
	static class Interval{
		int start, end;
		Interval(int x, int y){
			this.start = x;
			this.end = y;
		}
	}
	
	public static void main(String[] args){
		Interval[] data = {new Interval(1,3), new Interval(2,5), new Interval(8,9)};
		System.out.println(findRange(data));
		
	}
}

Can you count big O for your solution, or try to start your solution with int[,] tuples = new int[,] {{0,int.MaxValue}};

Can someone please explain the questions? How is the answer for [(1,3), (2,5),(8,9)] is 5? What exactly are we supposed to find out?

Think of it as intervals on the number line, and the problem is asking for the range that all these intervals cover.
to give you an specific example:
[(1,3)] will cover a range of 2
[(1,3), (2, 5)] will cover 4
[(1,3), (4, 5), (7,10)] will cover 6.

bool pair_compare(const std::pair<int,int> &a, const std::pair<int,int> &b) {
return a.first < b.first;
}

int covered_interval(std::vector<std::pair<int, int> > pairs) {
int n = pairs.size();
if (n == 0) {
return -1;
}

std::sort(pairs.begin(), pairs.end(), pair_compare);

int i = 1;
int sum = 0;
int begin = pairs[0].first;
int end = pairs[0].second;

while (i < n) {
std::pair<int, int> pair = pairs[i];
if (pair.first > end) {
sum += end - begin;
begin = pair.first;
end = pair.second;
} else {
if (end < pair.second) {
end = pair.second;
}
}
i++;
}

sum += end - begin;
return sum;
}

public class Point implements Comparable<Point>{
	int x;
	int y;

	public Point() {
		this(0, 0);
	}

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Point other) {
		if (this.y == other.y) return 0;
		return this.y < other.y ? -1 : 1;
	} 
}

public int findRangeOfIntervals(Point[] points) {
		List<Point> list = Arrays.asList(points);
		Collections.sort(list);
		int lowerBound = -1;
		int upperBound = -1;
		int result = 0;

		for (int i = 0; i < list.size(); i++) {
			Point p = list.get(i);
			if (p.x <= upperBound) {
				if (p.y > upperBound) {
					upperBound = p.y;
				}
			} else {
				lowerBound = p.x;
				upperBound = p.y;
			}

			if (result < upperBound - lowerBound) {
				result = upperBound - lowerBound;
			}
		}

		return result;
	}

class Tuple
{
public:
        Tuple(int a, int b):a(a), b(b){}
        Tuple(const Tuple& t): a(t.a), b(t.b){}
        int a;
        int b;
};

bool compare(const Tuple& t1, const Tuple& t2)
{
        return t1.a < t2.a;
}

Tuple findMaxRange(vector<Tuple>& V){
        if(V.size() == 1)
                return V[0];
        //assert(V.size() > 0);
                                  
        sort(V.begin(), V.end(), compare);
        Tuple max(V[0]);
        Tuple cur(V[0]);

        for(int i=1; i<V.size(); ++i){
                Tuple& tmp = V[i];
                if(cur.b >= tmp.a && cur.b < tmp.b) {
                        cur.b = tmp.b;
                        if((cur.b-cur.a) > (max.b-max.a))
                                max = cur;
                }
                if(cur.b < tmp.a)
                        cur = tmp;
        }

        return max;

}

class Tuple
{
public:
        Tuple(int a, int b):a(a), b(b){}
        Tuple(const Tuple& t): a(t.a), b(t.b){}
        int a;
        int b;
};

bool compare(const Tuple& t1, const Tuple& t2)
{
        return t1.a < t2.a;
}

Tuple findMaxRange(vector<Tuple>& V){
        if(V.size() == 1)
                return V[0];
        //assert(V.size() > 0);
                                  
        sort(V.begin(), V.end(), compare);
        Tuple max(V[0]);
        Tuple cur(V[0]);

        for(int i=1; i<V.size(); ++i){
                Tuple& tmp = V[i];
                if(cur.b >= tmp.a && cur.b < tmp.b) {
                        cur.b = tmp.b;
                        if((cur.b-cur.a) > (max.b-max.a))
                                max = cur;
                }
                if(cur.b < tmp.a)
                        cur = tmp;
        }

        return max;
}

I just used as hashset to store the int values in each interval and returned the hashset count.

protected int GetCoverageOfIntervals()
    {
        int[,] tuples = new int[,] {{1,3}, {2,5}, {8,9} };
        HashSet<int> covered = new HashSet<int>();
        int i = 0; 

        while (i < (int)(tuples.Length/2))
        {
            for (int j = tuples[i, 0]; j < tuples[i, 1]; j++)
                covered.Add(j);
            i++;
        }
        return covered.Count;
    }