2

I have a list of BaseBallGame objects with start and end time. I need to make sure that each game are happening at a separate time so that a user can watch the live stream of all the game.

I have an algorithm of O(n^2). I need to at least make it nlog(n). Can someone give me a pointer on how we can improve the performance of my implementation?

public class GameTime {

    public static Boolean canViewAll(Collection<BaseBallGame> baseBallGames) {

        List<BaseBallGame> games_list = (List<BaseBallGame>) baseBallGames;
        boolean isOverlap = false;

        for (int i = 0; i < games_list(); i++) {

            for (int j = i + 1; j < games_list(); j++) {

                Date startA = games_list(i).getStart();
                Date endA = games_list(i).getEnd();
                Date startB = games_list(j).getStart();
                Date endB = games_list(j).getEnd();

                boolean isStartABeforeEndB = (startA.compareTo(endB)) < 0;
                boolean isEndAAfterStartB = (endA.compareTo(startB)) > 0;

                boolean isCurrentPairOverlap = false;

                isCurrentPairOverlap = isStartABeforeEndB && isEndAAfterStartB;

                if (isCurrentPairOverlap) {
                    isOverlap = true;
                }
            }
        }
        return !isOverlap;
    }

    boolean overlap(Date start1, Date end1, Date start2, Date end2){
        return start1.getTime() <= end2.getTime() && start2.getTime() <= end1.getTime();
    }

    public static void main(String[] args) throws Exception {
        SimpleDateFormat sdf = new SimpleDateFormat("y-M-d H:m");

        ArrayList<BaseBallGame> baseBallGames = new ArrayList<BaseBallGame>();
        baseBallGames.add(new BaseBallGame(sdf.parse("2015-01-01 20:00"), sdf.parse("2015-01-01 21:30")));
        baseBallGames.add(new BaseBallGame(sdf.parse("2015-01-01 21:30"), sdf.parse("2015-01-01 23:00")));
        baseBallGames.add(new BaseBallGame(sdf.parse("2015-01-01 23:10"), sdf.parse("2015-01-01 23:30")));

        System.out.println(GameTime.canViewAll(baseBallGames));
    }
}

class BaseBallGame {
    private Date start, end;

    public BaseBallGame(Date start, Date end) {
        this.start = start;
        this.end = end;
    }

    public Date getStart() {
        return this.start;
    }

    public Date getEnd() {
        return this.end;
    } 

}

5 Answers 5

5

You are describing the Activity Selection Problem

  1. Sort the list based on the finish time.
  2. Iterate the list and check if the start time of A[i+1] is greater than the end time of A[i].

And since it involves sorting it has a O(n log n)

1
  • This seems like the perfect solution so I am going to give this a try.
    – Fawzan
    Nov 14, 2017 at 4:53
1

What if you were to sort the list using a Comparator and then iterate through the list once and see if any times overlap?

Java Array Sorting Algorithm: java.util.Arrays uses mergesort for objects that implement Comparable or use a Comparator.

Merge sort algorithm is average/best/worst case nlog(n). Then, the one iteration through would be negligible.

1
  • It's not about number because mergesort is much slower then quicksort. That's the reason i never use BigO because it's harmful. Mergesort has aux array which makes it slow. Nov 14, 2017 at 5:19
0

There are a bunch of sorting algorithms, you can implement them in your code. The below sorting algorithms on the websites have been implemented and also show the time complexity.

https://www.toptal.com/developers/sorting-algorithms

The Quicksort and Quicksort 3 way partition are nlogn algorithms.

0

if you just want to check whether there is a clash, Then you can try

Set<BaseBallGame> baseBallGameSet = new HashSet<BaseBallGame>(games_list);
if(baseBallGameSet.size < games_list.size)
  // Clash exists.

You can consider this as an optimization before what @thebenman has suggested.

0

The most efficent algorithm to adapt this problem is interval search tree. You have beginning time and endtime, means you have an intervals. Once your game starts and if it does not overlap the time of other game then put it in the tree. When you start a new game then put that game time and if it overlaps the time of previous game then tree will report because it has an interscetion.

The tree looks like this: enter image description here.

Instead of checking for everytime for a new game , all you need is to put your interval in tree, if it intersect an other interval then tree datastructure will automatically detect it and report it. Time complexity of this algorithm for insertion and deletion is ~logN which super efficient. If you have R intersections then the complexity will be ~RlogN where R are number of intersections.

You can also follow video of robert sedgewick here.

Your Answer

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

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