import java.util.*;
class Interval {
  public int start;
  public int end;
  public int cost;
  public Interval(int start, int end, int cost){
    this.start = start;
    this.end = end;
    this.cost = cost;
  }
}
public class BestCombinationFinder {
  public int getBestCombination(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
      return 0;
    }
    Collections.sort(intervals, new Comparator<Interval>() {
      public int compare(Interval i1, Interval i2) {
        if (i1.end < i2.end) {
          return -1;
        }
        else if (i1.end > i2.end) {
          return 1;
        }
        return 0;
      }
    });
    return findBestCombination(intervals);
  }
  private int findBestCombination(List<Interval> intervals) {
    int[] dp = new int[intervals.size() + 1];
    for (int i = 1; i <= intervals.size(); i++) {
      Interval currInt = intervals.get(i - 1);
      int pIndex = find(intervals, currInt.start, 0, intervals.size() - 1);
      dp[i] = Math.max(dp[pIndex+1] + currInt.cost, dp[i - 1]);
    }
    return dp[intervals.size()];
  }
  private int find(List<Interval> intervals, int target, int left, int right) {
    if (left > right) {
      return right;
    }
    else {
      int mid = (left + right) / 2;
      if (intervals.get(mid).end == target) {
        return mid;
      }
      else if (intervals.get(mid).end > target) {
        return find(intervals, target, left, mid - 1);
      }
      else {
        return find(intervals, target, mid + 1, right);
      }
    }
  }
}

One could implement this in O(nlogn)

Steps:

1. Sort the intervals based on end time
2. define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn
3. define d[i] = max(w(i) + d[p(i)], d[i-1]).

initialize d[0] = 0

The result will be in d[n] n- the number of intervals.

Overall complexity O(nlogn)

One could implement this in O(nlogn)

Steps:

1. Sort the intervals based on end time
2. define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn
3. define d[i] = max(w(i) + d[p(i)], d[i-1]).

initialize d[0] = 0

The result will be in d[n] n- the number of intervals.

Overall complexity O(nlogn)