Skip to content

Instantly share code, notes, and snippets.

@jcsirot jcsirot/Rental.java
Created Feb 19, 2013

Embed
What would you like to do?
package com.chelonix.codestory.jajascript;
import java.util.List;
/**
* ...
*
* @author sirot
*/
public interface Rental
{
int evaluate(List<Request> requests);
Path evaluatePath(List<Request> requests);
}
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);
}
}
// $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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.