1
\$\begingroup\$

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

  }
}
\$\endgroup\$
1

1 Answer 1

3
\$\begingroup\$

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;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.