Finding overlapping time intervals for two games

Question

I am trying to learn Java by doing some (easy) ACM TCPC problems. The problem is finding number of overlapping times intervals. If there a one, a fight will happen between the two games connected to those intervals.

Example

Input

1 // this is the number of cases.
3 // the number of time intervals
1 5 // The first intervals is [1, 5]
1 2 // ...
2 4

The comment are mine.

Output:

Case 1: 3

I'm looking for a review in terms of best practices, things I should or shouldn't do, or things I should do in another way.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class Compo {
 public static void main(String[] args) throws IOException {
 File fin = new File("./compo.in");
 numberOfFight(fin);
 }
 private static int numberOfFight(File fin) throws IOException {
 try (BufferedReader br = new BufferedReader(new FileReader(fin))) {
 int numberOfCases = Integer.parseInt(br.readLine());
 int i = 0;
 int numberOfGame = 0;
 String line;
 while (i < numberOfCases) {
 numberOfGame = Integer.parseInt(br.readLine());
 List<int[]> games = new ArrayList<int[]>(numberOfGame);
 for (int j = 0; j < numberOfGame; j++) {
 line = br.readLine();
 int[] game = new int[2];
 game[0] = Integer.parseInt(line.split(" ")[0]);
 game[1] = Integer.parseInt(line.split(" ")[1]);
 games.add(game);
 }
 int fights = 0;
 for (int j = 0; j < numberOfGame - 1; j++) {
 for (int k = j + 1; k < numberOfGame; k++) {
 if (fight(games.get(j), games.get(k))) {
 fights++;
 }
 }
 }
 i++;
 System.out.println("Case "+i+": "+fights);
 }
 }
 return 0;
 }
 private static boolean fight(int[] game1, int[] game2) {
 // Check if the games overlap
 return ((game1[0] <= game2[0]) && (game2[0] <= game1[1])) || ((game1[0] <= game2[1]) && (game2[1] <= game1[1]));
 }
}

• Vogel612: Welcome to Code Review! Links can rot. Please include a description of the problem here in your question.

Answer 1

Depends on what you want. Typically programming challenges are not validated on clean code. But on correctness and efficiency.

Use libraries:

You are having a lot of duplicate code, parsing numbers. Check out the Scanner class which has these methods builtin.

https://docs.oracle.com/javase/8/docs/api/java/util/Scanner.html

Remark: When efficiency is important, Scanner may be a lot slower than BufferedReader. In this case I still recommend putting the one time effort of creating your own custom read methods.

Efficiency:

You are looping over all intervals. This means you have to check all intervals with each other. Hence complexity: O(N2)

This is a well known problem, you could find a lot of reading about this online if you want.

General:

Write your overlap with less comparissons.

// overlaps when A starts before B ends AND B starts before A ends
private static boolean fight(int[] game1, int[] game2) {
 return game1[0] < game2[1] && game2[0] < game1[1]; 
}

For readability I would recommend create a class instead of working with int[2]. Typos are sometimes difficult to track.

class Game
{
 private int start;
 private int end;
 public Game(int start, int end)
 {
 this.start = start;
 this.end = end;
 }
 public bool overlaps(Game other)
 {
 return this.start < other.end && other.start < this.end;
 }
}