Dados N equipos y los resultados del torneo de todos contra todos en los que no resultó ningún partido es empate o empate. La tarea es encontrar el orden de los equipos de modo que cada equipo haya ganado contra su equipo consecutivo.
Ejemplos:
Entrada: N = 4
resultados[] = {{1, 4}, {4, 3}, {2, 3}, {1, 2}, {2, 1}, {3, 1}, {2, 4 }}
Salida: 2 4 3 1
Explicación:
El Equipo-2 ha ganado contra el Equipo-4, en el último partido.
El Equipo-3 ha perdido ante el Equipo-4 en el segundo partido y
el Equipo-3 ganó contra el Equipo-1 en el penúltimo partido.
Por lo tanto, cada equipo ha ganado contra el equipo de al lado.Entrada: N = 5
resultados[] = {{1, 4}, {4, 3}, {2, 3}, {1, 2}, {2, 1},
{3, 1}, {4, 2 }, {2, 5}, {5, 3}, {4, 5}, {5, 1}}
Salida: 4 2 5 3 1
Enfoque: la idea es mantener un mapa hash para cada equipo que almacene los equipos contra los que el equipo ha ganado en el torneo de todos contra todos. Esto se puede hacer iterando sobre los elementos de los resultados y para cada ganador agregándolo a la lista del objeto de mapa hash de ese equipo.
The hashtable for an example is as follows: Key Value Team-1 => [Team-4, Team-2] Team-2 => [Team-3, Team-1, Team-4] Team-3 => [Team-1] Team-4 => [Team-3]
Finalmente, calcule el orden de los equipos usando recursivamente. A continuación se muestra la ilustración de la función recursiva:
- Caso base: cuando la longitud actual de los equipos es 1, devuelva el equipo.
- Caso recursivo: calcule el orden del equipo N – 1 y después del cálculo de los equipos, itere sobre el orden de los equipos y encuentre una posición en la que el equipo actual haya perdido contra su equipo anterior. Si no existe tal posición, agregue el equipo en la última posición.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation to find the
// order of the teams in a round
// robin tournament such that every
// team has won against to its next team
import java.util.*;
import java.lang.*;
// A class to represent result
// of a match of a tournament.
class Result {
int winner;
int loser;
Result(int winner, int loser)
{
this.winner = winner;
this.loser = loser;
}
}
public class TeamOrdering {
// Function to arrange the teams of
// the round-robin tournament
static void arrangeTeams(int[] teams,
Result[] results)
{
HashMap<Integer,
List<Integer> >
map = new HashMap<>();
int winner = 0;
// Creating a hashmap of teams
// and the opponents against
// which they have won, using
// the results of the tournament
for (int i = 0; i < results.length; i++) {
winner = results[i].winner;
if (map.containsKey(winner)) {
map.get(winner).add(
results[i].loser);
}
else {
List<Integer> list
= new ArrayList<Integer>();
list.add(results[i].loser);
map.put(winner, list);
}
}
List<Integer> output = new ArrayList<>();
// Arrange the teams in required order
setInOrder(teams, map, teams.length, output);
Iterator<Integer> it = output.iterator();
// Displaying the final output
while (it.hasNext()) {
System.out.print(it.next());
System.out.print(" ");
}
}
// Function to determine
// the order of teams
static void setInOrder(
int[] teams,
HashMap<Integer, List<Integer> > map,
int n, List<Integer> output)
{
// Base Cases
if (n < 1) {
return;
}
// If there is only 1 team,
// add it to the output
else if (n == 1) {
output.add(teams[n - 1]);
return;
}
// Recursive call to generate
// output for N-1 teams
setInOrder(teams, map, n - 1, output);
int key = teams[n - 1];
int i;
// Finding the position for the
// current team in the output list.
for (i = 0; i < output.size(); i++) {
// Obtain the team at current
// index in the list
int team = output.get(i);
// Check if it has lost against
// current team
List<Integer> losers = map.get(key);
if (losers.indexOf(team) != -1)
break;
}
// Add the current team
// to its final position
output.add(i, key);
}
// Driver Code
public static void main(String[] args)
{
int[] teams = { 1, 2, 3, 4 };
Result[] results = {
new Result(1, 4),
new Result(4, 3),
new Result(2, 3),
new Result(1, 2),
new Result(2, 1),
new Result(3, 1),
new Result(2, 4)
};
// Function Call
arrangeTeams(teams, results);
}
}
2 4 3 1
Análisis de rendimiento:
- Complejidad del tiempo: O(N 2 )
- Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por CharchitKapoor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA