@@ -0,0 +1,1696 @@
+package dynamic;%0D%0A%0D%0Aimport java.io.File;%0D%0Aimport java.io.FileNotFoundException;%0D%0Aimport java.util.ArrayList;%0D%0Aimport java.util.Arrays;%0D%0Aimport java.util.Collections;%0D%0Aimport java.util.Comparator;%0D%0Aimport java.util.Scanner;%0D%0A%0D%0Apublic class IntervalSchedule %7B%0D%0A    public static class Interval %7B%0D%0A%09public int start;%0D%0A%09public int end;%0D%0A%09public int weight;%0D%0A%0D%0A%09public Interval() %7B%0D%0A%09    start = 0;%0D%0A%09    end = 0;%0D%0A%09    weight = 0;%0D%0A%09%7D%0D%0A%0D%0A%09public Interval(int s, int e, int w) %7B%0D%0A%09    start = s;%0D%0A%09    end = e;%0D%0A%09    weight = w;%0D%0A%09%7D%0D%0A%0D%0A%09public String toString() %7B%0D%0A%09    return %22%5B%22 + start + %22,%22 + end + %22,%22 + weight +%22%5D%22;%0D%0A%09%7D%0D%0A    %7D%0D%0A    %0D%0A    %0D%0A    public int schedule(ArrayList%3CInterval%3E input) %7B%0D%0A%09Comparator%3CInterval%3E myC = new Comparator%3CInterval%3E() %7B%0D%0A%09    public int compare(Interval a, Interval b) %7B%0D%0A%09%09    return a.end - b.end;%0D%0A%09%09%7D%0D%0A%09%7D;%0D%0A%09%0D%0A%09Collections.sort(input, myC);%0D%0A%09int%5B%5D start = new int%5Binput.size()%5D;%0D%0A%09int%5B%5D end = new int%5Binput.size()%5D;%0D%0A%09for(int i = 0; i %3C input.size(); i++)%7B%0D%0A%09    start%5Bi%5D=input.get(i).start;%0D%0A%09    end%5Bi%5D=input.get(i).end;%0D%0A%09%7D%0D%0A%09%0D%0A%09int%5B%5D dp = new int%5Binput.size()+1%5D;%0D%0A%09dp%5B0%5D=0;%0D%0A%09dp%5B1%5D=input.get(0).weight;%0D%0A%09for(int i = 2;i %3C= input.size(); i++)%7B%0D%0A%09    int left = bsless(end, start%5Bi-1%5D);%0D%0A%09    if(left != -1)%0D%0A%09%09dp%5Bi%5D = Math.max(dp%5Bi-1%5D, input.get(i-1).weight + dp%5Bleft%5D);%0D%0A%09    else%7B%0D%0A%09%09dp%5Bi%5D = Math.max(dp%5Bi-1%5D, input.get(i-1).weight);%0D%0A%09    %7D%0D%0A%09%7D%0D%0A%09return dp%5Binput.size()%5D;%0D%0A    %7D%0D%0A    %0D%0A    //may vary, depend on whether the start and end can be one point?%0D%0A    public int bsless(int%5B%5D a, int x)%7B%0D%0A%09int l = 0;%0D%0A%09int r = a.length - 1;%0D%0A%09while(l %3C r)%7B%0D%0A%09    int m = (l + r) /2 ;%0D%0A%09    if(a%5Bm%5D %3C x) l = m+1;%0D%0A%09    else r = m;%0D%0A%09%7D%0D%0A%09return l-1;%0D%0A    %7D%0D%0A%7D%0D%0A

add weighted interval scheduling