[Solved] Algorithm for achieving best finish time for a team in a triathlon race [closed]

by


You just need to worry about two simple rules :

  1. If we send the contestant that takes the least amount of time to swim first, we are reducing the finish time between contestants.
  2. What if two contestants have the same swim time? In this case, the contestants who have a higher total running + cycling time should be sent first so that they can get a head start for the remaining activities.

Consider the time each contestant takes for a particular activity:

Contestant->Swim time(mins)->Run time(mins)->Cycle time(mins)
A->1->1->1
B->2->1->1
C->1->1->1

Case 1 :
Contestant with maximum swim time goes first. Race starts at 12:00 PM in the order B, A, C, we have :

Swimming complete->Running complete->Cycling complete
B->12:02->12:03->12:04
A->12:03->12:04->12:05
C->12:04->12:05->12:06

Case 2 :
Contestant with maximum swim time goes second. Race starts at 12:00 PM in the order A, B, C, we have :

Swimming complete->Running complete->Cycling complete
A->12:01->12:02->12:03
B->12:03->12:04->12:05
C->12:04->12:05->12:06

Case 3 :
Contestant with maximum swim time goes third. Race starts at 12:00 PM in the order A, C, B we have :

Swimming complete->Running complete->Cycling complete
A->12:01->12:02->12:03
C->12:02->12:03->12:04
B->12:04->12:05->12:06

You can see that in all the cases, the last contestant finishes the race at 12:06. However, in Case 1 (Contestant with maximum swim time goes first), the first contestant finishes at 12:04 PM and second contestant finishes at 12:05. In case two (Contestant with maximum swim time goes second), the first contestant finishes the race at 12:03 and the second contestant at 12:05. In case 3 (Contestant with maximum swim time goes third), the first contestant finishes the race at 12:03 and the second contestant finishes the race at 12:04. This is by far the most efficient order since by 12:04, you already have two contestants who have finished the race.

But what if two contestants have the same swim time but different cycle and run time. Consider :

Contestant->Swim time(mins)->Run time(mins)->Cycle time(mins)
A->1->1->1
B->2->2->1
C->2->1->1

Case 4 : From the two contestants with the same swimming time, the contestant with a lower total of cycling and running time goes first :

Swimming complete->Running complete->Cycling complete
A->12:01->12:02->12:03
C->12:03->12:04->12:05
B->12:05->12:07->12:08

Case 5 : From the two contestants with the same swimming time, the contestant with a higher total of cycling and running time goes first :

Swimming complete->Running complete->Cycling complete
A->12:01->12:02->12:03
B->12:03->12:05->12:06
C->12:05->12:06->12:07

As can be seen, the last contestant finishes the race at 12:08 PM in case 4 whereas the last contestant finishes the race at 12:07 in case 5. This implies that if two contestants have the same swim time, the contestant with the higher total of cycling+running time should go first.

To code this in Java :

First create a class to hold contestant information : 

public class Contestant {
    private String name;
    private Map<String,Integer> timings = new HashMap<>();

    public Contestant(String name, Map<String, Integer> timings) {
        this.name = name;
        this.timings = timings;
    }

    public Integer getTimingFor(String activity) {
        return timings.get(activity);
    }

    public Map<String, Integer> getTimings() {
        return timings;
    }

    public String getName() {
        return name;
    }


}

Then create a Comparator that will decide which contestant should go before another contestant. The idea is to order the contestants in the order of swimming time (ascending) and then in the order of the remaining activities (descending)

  public class ContestantComparator implements Comparator<Contestant> {

    @Override
    public int compare(Contestant one, Contestant two) {
        int contestantOneSwimTime = one.getTimingFor("Swimming");
        int contestantTwoSwimTime = two.getTimingFor("Swimming");

        if(contestantOneSwimTime<contestantTwoSwimTime) {
            return -1;
        } else if(contestantOneSwimTime>contestantTwoSwimTime) {
            return 1;
        } else {
            int c1RemainingTimeExceptSwimming = 0;
            int c2RemainingTimeExceptSwimming = 0;

            for(String activity : one.getTimings().keySet()) {
                if(!activity.equals("Swimming")) {
                    c1RemainingTimeExceptSwimming+=one.getTimingFor(activity);
                }
            }

            for(String activity : two.getTimings().keySet()) {
                if(!activity.equals("Swimming")) {
                    c2RemainingTimeExceptSwimming+=two.getTimingFor(activity);
                }
            }

            if(c1RemainingTimeExceptSwimming>c2RemainingTimeExceptSwimming) {
                return -1;
            } else if(c1RemainingTimeExceptSwimming<c2RemainingTimeExceptSwimming) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}

Main class to use the code :

public class Contest {

    public static void main(String []args) {
        Map<String,Integer> timings = new HashMap<String,Integer>();
        timings.put("Swimming", 1);
        timings.put("Running", 1);
        timings.put("Cycling", 1);
        Contestant a = new Contestant("A",timings);

        timings = new HashMap<String,Integer>();
        timings.put("Swimming", 1);
        timings.put("Running", 2);
        timings.put("Cycling", 1);
        Contestant b = new Contestant("B",timings);

        timings = new HashMap<String,Integer>();
        timings.put("Swimming", 1);
        timings.put("Running", 2);
        timings.put("Cycling", 2);
        Contestant c = new Contestant("C",timings);

        List<Contestant> contestants = new ArrayList<Contestant>();
        contestants.add(a);
        contestants.add(b);
        contestants.add(c);
        Collections.sort(contestants,new ContestantComparator());

        for(Contestant contestant : contestants) {
            System.out.println(contestant.getName());
        }

    }

}

Note that the Contestant class contains a Map. The purpose of this map is to allow you to add any number of tasks for the contestants without the need to change your code. The key represents the activity such as swimming and the value (Integer) represents the time for the corresponding activity.

5

solved Algorithm for achieving best finish time for a team in a triathlon race [closed]