Attend Meetings Problem

Given a list of meeting time intervals consisting of start and end times [[s1, e1], [s2, e2], …] (si < ei). You need to complete canAttendAllMeetings function and return 1 if a person can attend all given meetings else 0.

Input Format:

There is only one argument in input, list of intervals (Each interval is a list containing two elements where the first element is the start time of that interval and the second element is the end time of that interval).

Output Format:

Return either a 1 or a 0.

Solutions

We have provided a solution which contains necessary comments to understand the approach used: solution.java

Description:

We are asked to determine whether a person can attend all meetings represented by a list of given intervals or not.

In brute force method, we can iterate over each interval and try to find another overlapping interval with the current interval. As this process will take two loops and hence will lead to O(n^2) time complexity.

Hence to optimise, we sort the given array by start time of intervals and if start time are same then we sort by end time of intervals.

As intervals are sorted, we can easily observe a relation between end time of previous interval to start time of current interval to determine overlap. If previous_end time > current start time that means previous and current are overlapping intervals. Hence we will return 0 else else continue to iterate. Here if current means ith interval then previous means i-1th interval.

For better understanding, please have a look at the solution.

Time Complexity:

O(n log n) where n denotes the number of intervals.

As we are sorting list of n intervals hence it will take O(n log n) time. After sorting we are iterating over n intervals it will take O(n) time. Hence the total time complexity will be O(n log n) + O(n) → O(n log n).

Auxiliary Space Used:

O(1).

We are not storing anything extra. We are assuming that sorting of n intervals will be in place hence O(1).

Space Complexity:

O(n) where n denotes the number of intervals.

To read input it will take O(n) as we are reading n intervals, auxiliary space used is O(1) and to store output it will take O(1) hence total space complexity will be O(n).

// -------- START --------
    public static int canAttendAllMeetings(List<list> intervals){
        // Sorting in ascending order of start value of an interval
        // if start value is same for two intervals then sort in ascending order of end value of intervals
        Collections.sort(intervals, new Comparator<list>() {
            @Override
            public int compare(List l1, List l2) {
                if (l1.get(0) - l2.get(0)!= 0) {
                    return (int)(l1.get(0) - l2.get(0));
                }
                return (int)(l1.get(1) - l2.get(1));
            }
        });
        // As intervals have at least one element
        int previous_end = intervals.get(0).get(1);
        for (int i=1; i<intervals.size(); 0 i++){   we compare previous intervals's end with current interval's start if this condition satisfied means overlap and return  if (previous_end> intervals.get(i).get(0)) {
                return 0;
            }
            // Updated previous' end.
            previous_end = intervals.get(i).get(1);
        }
        return 1;
    }
    // -------- END --------