CareerCup

O(nlgn) using Activity Selection Problem:

1) Sort the pairs according to their second element --> O(nlgn)
2) Select the first pair from the sorted array and print it. --> O(1)
3) Do following for remaining pairs in the sorted array. --> O(n)
---------------> If the first element of this pair is greater than the 2nd element of previously selected pair then select this pair and print it.

public static int LongestChainPairs(Pair[] pairs)
{
	Collection.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
	int chainLength = 0;
	
	//select the first pair of the sorted pairs array
	pairs[0].print(); //assume print method prints the pair as “(a, b) ”
	chainLength++;
	int prev = 0;

	for(int i=1;i<pairs.length; i++)
	{
		if(pairs[i].first >= pairs[prev].second)
		{
                pairs[i].print();
			chainLength++;
			prev = i;
		}
	}
	return chainLength;	
}

dynamic programming?

public static int findChain(int [] [] chain){
		int [] dp=new int [chain.length];
		
		dp [0] =1 ;
		int max =1 ;
		
		for (int i =1 ; i <chain.length ; ++i){
			if (chain[i][0]>chain[i-1][1]){
				dp [i]=dp[i]>dp[i-1]+1? dp [i] : dp[i-1]+1;
				max=Math.max(dp[i], max);
			}
		}
		return max;

}

Same as Longest Common Subsequence problem (just consider the second element in each pair) - can be solved in O(n^2) using dynamic programming.

Same as the "Scheduling Problem" in CLRS, which has a greedy algorithm solution.

Let's say input is a set of (x1,x2) points. Sort input by x2, then traverse the list and add elements to the chain which satisfy the required condition with regards to the tail of chain.

public static List<Pair> formChain(List<Pair> input) {
		Collections.sort(input, new PairEndComparator());
		LinkedList<Pair> chain = new LinkedList<>();
		for (Pair p : input) {
			if (chain.isEmpty() || chain.getLast().e < p.s)
				chain.add(p);
		}
		return chain;
	}

	static class PairEndComparator implements Comparator<Pair> {
		public int compare(Pair p1, Pair p2) {
			return p1.e - p2.e;
		}
	}

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


public class Chain {

	class Segment implements Comparable<Segment> {

		private final int start;
		private final int end;
		private final String name;
		
		public int getStart() {
			return start;
		}

		public int getEnd() {
			return end;
		}

		public String getName() {
			return name;
		}

		Segment(int start, int end, String name) {
			this.start = start;
			this.end = end;
			this.name = name;
		}
		
		@Override
		public int compareTo(Segment s) {
			
			if (this.end > s.end) {
				return 1;
			} else if (this.end == s.end){
				return 0;				
			} else {
				return -1;
			}
				
		}
		
	}
	
	
	private final Segment[] segments = {
			
			new Segment( 8, 10, "A" ),
			new Segment( 0, 7, "B" ),
			new Segment( 11, 12, "C" ),
			new Segment( 13, 16, "D" ),
			new Segment( 0, 1, "E" ),
			new Segment( 2, 15, "F" ),
			new Segment( 4, 11, "G" ),
			new Segment( 5, 6, "H")
	};
	
	
	public int findChainLength() {
		
		List<Segment> tempSegments = new LinkedList<Segment>();
		int result = 0;
		
		
		for (Segment s : segments) {
			tempSegments.add(s);
		}
		
		// O(nlogn) - sort segments by their end points:
		Collections.sort(tempSegments);
		Segment[] sortedSegments = (Segment[])tempSegments.toArray(new Segment[tempSegments.size()]);
		
		int currentSegmentIndex;
		
		currentSegmentIndex = 0;
		System.out.print(sortedSegments[currentSegmentIndex].getName());
		result++;
		
		// O(n) worst case - scan and augment chain by adding the next
		// shortest segment:
		for (int index = 1; index < tempSegments.size(); index++) {
			
			if (sortedSegments[index].getStart() > sortedSegments[currentSegmentIndex].getEnd()) {
				currentSegmentIndex = index;
				result++;
				
				System.out.print(sortedSegments[currentSegmentIndex].getName());
			}
		}
		
		return  result;
	}
	
	
	public static void main(String[] args) {
		
		Chain myChain = new Chain();
		
		myChain.findChainLength();
		
		return;
	}
}

1) Sort the sets on the basis of second number. Set (a,b) should be sorted on 'b'
2) Then, take the series satisfying second condition, that is, out of sets (a,b) & (c,d) b should be less than c.

For example,
(4,5) (7,9) (1,2) (11,15) (3,18)
After sorting it becomes:
(1,2)
(4,5)
(7,9)
(11,15)
(3,18)
It is being assured that in (a,b) a is always less than b.
Now, we can choose elements with respect to second condition as out of two sets, (a,b) & (c,d) b should be less than c.

this can be solved like the greedy approach of latest finish time job first.
in that we have to schedule the most no. of jobs which is here analogous to longest chain.
first we sort the pairs according to their second number. then we chose the first pair and then the next pair is next first pair in that sorted list such that its first number is. greater than second number of the previous chosen pair.

This guy must be interviewing with several companies everyday.