finding the conflicts in meetings given startTimes and end Times

Question

Code to find conflicts in a list of meetings given as input. Meetings are defined as {startTime, endTime}. I am using a Greedy Algorithm to find the conflicts. Wanted to know if there is a more efficient way of solving this problem.

Example:

Input: `meetings[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}`  
Output: Number of Conflicts : 4

The code:

// Meeting Class
class Meeting implements Comparable<Meeting> {
    int startTime;
    int endTime;
    public Meeting(int startTime, int endTime) {
        super();
        this.startTime = startTime;
        this.endTime = endTime;
    }
    @Override
    public int compareTo(Meeting o) {
        if(this.startTime == o.startTime) return 0;
        if(this.startTime < o.startTime) return -1;
       return 1;
    }

}

Class which computes the conflicts

public class FindConflictingMeetingsProblem {
     // static function to find conflicts
    public static int findNumberOfConflicts(List<Meeting> meetings){

        // sort the meetings in ascending order of start time
        Collections.sort(meetings,new Comparator<Meeting>(){
            @Override
            public int compare(Meeting o1, Meeting o2) {
                return o1.compareTo(o2);
            }
        });

        int conflicts = 0;
        // count the conflicts
        for(int i = 0 ; i < meetings.size();i++){
            if(i > 1 && meetings.get(i-1).endTime > meetings.get(i).startTime){
                conflicts++;
            }
        }
        return conflicts;
    }

    public static void main(String[] args) {
            Meeting m1 = new Meeting(1, 2);
            Meeting m2 = new Meeting(2, 5);
            Meeting m4 = new Meeting(4, 5);
            Meeting m5 = new Meeting(7, 8);
            List<Meeting> meetingsList = new ArrayList<Meeting>();
            meetingsList.add(m1);
            meetingsList.add(m2);
            meetingsList.add(m4);
            meetingsList.add(m5);
            System.out.println(" Number of conflicts :"+findNumberOfConflicts(meetingsList));
     }
}

Answer 1

Advice 1

int startTime;
int endTime;

I suggest you hide them with private access modifier:

private int startTime;
private int endTime;

Advice 2

Elaborating on Advice 1 you can add the getters for the two above fields:

public int getStartTime() {
    return startTime;
}

...

Advice 3

 Collections.sort(meetings,new Comparator<Meeting>(){
                @Override
                public int compare(Meeting o1, Meeting o2) {
                    return o1.compareTo(o2);
                }
            });

Since you already have the compareTo method in your Meeting class, you can write more succinctly:

Collections.sort(meetings);

Advice 4

What comes to Meeting.compareTo, you can write shorter:

@Override
public int compareTo(Meeting o) {
    return Integer.compare(startTime, o.startTime);
}

Advice 5

Consider writing a method that tests whether two given meetings are conflicting each other:

public boolean conflictsWith(Meeting meeting) {
    if (endTime <= meeting.startTime) {
        return false;
    }

    if (meeting.endTime <= startTime) {
        return false;
    }

    return true;
}

Advice 6

Consider checking in the constructor of Meeting whether startTime <= endTime:

private void checkStartAndEndTimes(int startTime, int endTime) {
    if (startTime >= endTime) {
        throw new IllegalArgumentException("Start time (" + startTime + 
                ") >= end time (" + endTime + ").");
    }
}

Advice 7

public Meeting(int startTime, int endTime) {
                super();
                ...

Above super does not buy you anything, consider removing it.

Finally

The main algorithm is now a little bit more readable:

class FindConflictingMeetingsProblem {

    public static int findNumberOfConflicts(List<Meeting> meetings) {
        Collections.sort(meetings);
        int conflicts = 0;

        for (int i = 0; i < meetings.size() - 1; ++i) {
            if (meetings.get(i).conflictsWith(meetings.get(i + 1))) {
                conflicts++;
            }
        }

        return conflicts;
    }
}

Algorithm limitations

Consider this:

Meeting m1 = new Meeting(1, 10);
Meeting m2 = new Meeting(5, 9);
Meeting m3 = new Meeting(4, 7);
List<Meeting> meetingsList = new ArrayList<>();
meetingsList.add(m1);
meetingsList.add(m2);
meetingsList.add(m3);

The above will report 2, but there is 3 pairs of meetings that conflict each other.

Hope that helps.

Answer 2

1. The indentation of your code isn't good :s
2. I think making Meeting immutable would make for a better code
3. When an object is constructed it's usually a good idea to make sure it is correct, in your case you don't make any check over endTime and startTime (endTime must always be > to startTime), also super is useless here as you are only extending Object
4. You should hide the field with private modifiers
5. You can check the new java time objects (such as LocalDateTime if you don't want to be bothered by time-zone) instead of using ints
6. In your findNumberOfConflicts : note that if a meeting conflicts with more than one other meeting(s), the result will be off
7. Still in your findNumberOfConflicts method : you should avoid modifying parameters as much as possible as it makes for harder to understand code, consider the following : Person p = new Person("Sarah", 19); foo(p); System.out.println(p.getName()); // if foo modifies its parameters it may print something like "Debug" which can be surprising for users

TreeSet are guaranteed to always be sorted so maybe findNumberOfConflicts can take a TreeSet as an argument ? If you want to only manipulate List then I'd recommend you to copy the input into another variable and then sort it.

Answer 3

Use what you have

                Collections.sort(meetings,new Comparator<Meeting>(){
                    @Override
                    public int compare(Meeting o1, Meeting o2) {
                        return o1.compareTo(o2);
                    }
                });

It's not clear why you need a Comparator.

                Collections.sort(meetings);

Meeting is already Comparable. You'd only need to make a Comparator if you wanted to customize the order somehow. Or if you wanted to sort objects that do not implement Comparable.

Use your bounds

                for(int i = 0 ; i < meetings.size();i++){
                    if(i > 1 && meetings.get(i-1).endTime > meetings.get(i).startTime){
                        conflicts++;
                    }
                }

The i > 1 is unnecessary.

            for (int i = 2; i < meetings.size(); i++) {
                if (meetings.get(i-1).endTime > meetings.get(i).startTime) {
                    conflicts++;
                }
            }

You can just start at 2 rather than 0. Then i will always be greater than 1.

Sorted data

                    List<Meeting> meetingsList = new ArrayList<Meeting>();

Consider instead

            NavigableSet<Meeting> meetings = new TreeSet<>();

You also might want to consider changing the sort order somewhat.

            @Override
            public int compareTo(Meeting o) {
                if(this.startTime == o.startTime) return 0;
                if(this.startTime < o.startTime) return -1;
               return 1;
            }

could be

        @Override
        public int compareTo(Meeting o) {
            if (startTime != o.startTime) {
                return Integer.compare(startTime, o.startTime);
            }

            return Integer.compare(endTime, o.endTime);
        }

So meetings with the same start time but different end times will have a definite order.