java - 比较同一列表中元素的高效算法

Question

我有一个包含开始和结束时间的 BaseBallGame 对象列表。我需要确保每场比赛都在不同的时间进行，以便用户可以观看所有比赛的直播。

我有一个O(n^2) 的算法。我至少需要让它成为 nlog(n)。有人可以指导我如何提高我的实现性能吗？

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

}

Answer 1

您正在描述 Activity Selection Problem

1. 根据完成时间对列表进行排序。
2. 迭代列表并检查 A[i+1] 的开始时间是否大于 A[i] 的结束时间。

因为它涉及排序，所以它有一个 O(n log n)