public static class FinishTimeComparator implements Comparator<Course>{

	    @Override
	    public int compare(Course arg0, Course arg1) {
	        if(arg0.finish <= arg1.finish){
	            return -1;
	        }else{
	            return 1;
	        }
	    }

	}


	public static class WeightedJobSchedulingMaximumProfit {

	    /**
	     * Sort the jobs by finish time.
	     * For every job find the first job which does not overlap with this job
	     * and see if this job profit plus profit till last non overlapping job is greater
	     * than profit till last job.
	     * @param jobs
	     * @return
	     */
	    public int maximum(Course[] arr){
	        int T[] = new int[arr.length];
	        FinishTimeComparator comparator = new FinishTimeComparator();
	        Arrays.sort(arr, comparator);

	        T[0] = arr[0].profit;
	        for(int i=1; i < arr.length; i++){
	            T[i] = Math.max(arr[i].profit, T[i-1]);
	            for(int j=i-1; j >=0; j--){
	                if(arr[j].finish <= arr[i].start){
	                    T[i] = Math.max(T[i], arr[i].profit + T[j]);
	                    break;
	                }
	            }
	        }
	        int maxVal = Integer.MIN_VALUE;
	        for (int val : T) {
	            if (maxVal < val) {
	                maxVal = val;
	            }
	        }
	        return maxVal;
	    }

	}