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]));

  }
}

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(N²)

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;
    }
}