Rental.java

package com.chelonix.codestory.jajascript;

import java.util.List;

/**
 * ...
 *
 * @author sirot
 */
public interface Rental
{
    int evaluate(List<Request> requests);

	Path evaluatePath(List<Request> requests);
}

RentalAlternative.java

package com.chelonix.codestory.jajascript;


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

/**
 * ...
 *
 * @author sirot
 */
public class RentalAlternative implements Rental
{
    public int evaluate(List<Request> requests)
	{
		return evaluatePath(requests).getSum();
	}

	public Path evaluatePath(List<Request> requests)
	{
		if (requests.isEmpty()) {
			return Path.EMPTY;
		}
		Collections.sort(requests);
		return computeBestPath(requests);
	}

	private Path computeBestPath(List<Request> requests)
	{
		List<Path> sortedPaths = new LinkedList<Path>();
		for (int i = requests.size() - 1; i>= 0; i--) {
			Request req = requests.get(i);
			Path path = new Path(req);

			for (Path candidate: sortedPaths) {
				if(req.isCompatibleWith(candidate.getHead())) {
					path = new Path(req, candidate);
					break;
				}
			}

			int k = 0;
			for(; k < sortedPaths.size(); k++) {
				Path p = sortedPaths.get(k);
				if (path.compareTo(p) >= 0) {
					break;
				}
			}
			sortedPaths.add(k, path);
		}
		return sortedPaths.get(0);
	}
}

Request.java

// $Id$
package com.chelonix.codestory.jajascript;

/**
 * ...
 *
 * @author sirot
 * @version $Revision$
 */
public final class Request implements Comparable<Request>
{
    private String id;
	private int start;
	private int length;
	private int price;

	public Request(String id, int start, int length, int price)
	{
		this.id = id;
		this.start = start;
		this.length = length;
		this.price = price;
	}

	public String getId()
	{
		return id;
	}

	public int getStart()
	{
		return start;
	}

	public int getLength()
	{
		return length;
	}

	public int getPrice()
	{
		return price;
	}

	@Override
	public String toString()
	{
		return "Request{" +
			"id='" + id + '\'' +
			", start=" + start +
			", length=" + length +
			", price=" + price +
			'}';
	}

	public boolean isCompatibleWith(Request o)
	{
		return (start + length) <= o.start;
	}

	public int compareTo(Request o)
	{
		if (this.start == o.start) {
			return 0;
		} else {
			return this.start > o.start ? 1 : -1;
		}
	}

	@Override
	public boolean equals(Object o)
	{
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;

		Request request = (Request) o;

		if (!id.equals(request.id)) return false;

		return true;
	}

	@Override
	public int hashCode()
	{
		return id.hashCode();
	}
}