CareerCup

O(nlogn) solution:
We're given an array of ranges.
We sort the ranges by lower range number with quicksort in O(nlogn) time and O(1) memory
Keep a counter of how many elements we will traverse
Then we pull the lowest range, increment counter by 1 and increment the lower range by 1. If that range's low > high then remove that array.
We then insert the new range back into the sorted array of arrays in O(n) time (most likely O(1) time because we pulled the lowest so we know it's probably one of the lowest still)
Stop when our counter is the kth element.

Here's O(nlogn + k) solution.
- Sort ranges by start
- keep index of next non empty range (rangeId) (initially pointing to smallest range)
- starting from lowest range get the start and set it to kth, incrementing k every time start of range is equal to current running kth and replacing range with a new range with start shifted by one. Once reached start > kth, break.
- When done with a range increment the lowest range index (rangeId)
repeat till k<K

import java.util.Collections;
import java.util.List;

public class KSmallestFromRanges {

	public int findKSmallest(List<Range> ranges, int K) {
		if (K<=0) {
			throw new IllegalArgumentException("K must be greater than zero");
		}
		Collections.sort(ranges);
		int rangeId = 0;
		int k = 0;
		int kth = -1;
		while (k < K) {
			if (rangeId >= ranges.size())  {
				break;
			}
			
			kth = ranges.get(rangeId).start;
			
			for (int firstRange = rangeId; firstRange<ranges.size(); firstRange++) {
				if (ranges.get(firstRange).start > kth) {
					break;
				}
								
				if ( (firstRange == rangeId) && 
						(ranges.get(firstRange).start + 1 > ranges.get(firstRange).end) ) { //this range is done
					rangeId++;
					k++;
					break;
				} else {
					if ( ! (ranges.get(firstRange).start  > ranges.get(firstRange).end )) { //skip a range if it is not the first but has already depleted
						ranges.set(firstRange, new Range(ranges.get(firstRange).start + 1, ranges.get(firstRange).end));
						k++;
					}
				}
			}
		}
		
		return kth;
		
	}
	
	public static class Range implements Comparable<Range>{
		int start;
		int end;
		
		public Range(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
		public int getStart() {
			return start;
		}
		public void setStart(int start) {
			this.start = start;
		}
		public int getEnd() {
			return end;
		}
		public void setEnd(int end) {
			this.end = end;
		}
		@Override
		public int compareTo(Range o) {
			if (this.start < o.start) {
				return -1;
			} else if (this.start > o.start) {
				return 1;
			} else {
				if (this.end < o.end) {
					return -1;
				} else {
					return 1;
				}
			}
		}
		@Override
		public String toString() {
			return "[" + start + ", " + end + "]";
		}
	}
}

1) use a minheap left bound as the key
2) get the top from heap and increase the number count until equals k
3) decrease the left bound and put back to heap unless left > right
O(nlogn)