Data Structures & Algorithms in Java – Intervals – Meeting Rooms

Problem:

Given an array of meeting time intervals (start time , end time) find if all the meetings could be attended.

For example,

Given the input array of intervals:

[[10,20],[15,30],[30,40]]

Return false because the meetings [10,20] and [15,30] overlap.

For the intervals

[[10,30],[40,50]]

Return true because the meetings don’t overlap

Try out the solution here:

https://leetcode.com/problems/meeting-rooms/

Advertisements

Solution:

Hint:

  • Sort the array of intervals by start time

The solution is straightforward

First sort the array by start time

Then compare the end time and start time of consecutive intervals.

If any of them overlap return false , else return true

ALGORITHM:

STEP 1: If interval size is 0 , return true

STEP 2: Sort the array based on start time

STEP 3: Iterate through the array and check if any of the intervals overlap (end of previous interval greater than start of current interval) .If so return false

STEP 4: Return true

Code:

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        
        if(intervals.length ==0) return true;
        
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
       
        for(int i=0;i<intervals.length-1;i++){
            
            if(intervals[i][1] > intervals[i+1][0]){
                return false;
            }
            
        }
        return true;
    }
}

Time complexity: O(nlogn) for the initial sorting plus the single iteration through the array

Space complexity: O(1) since there is no storage used in proportion to the input.

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s