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/

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!


Posted

in

, ,

by

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading