Java O(n) time solution using a priority queue.


  • -1
    Y

    This solution is O(n) time since the construction of a PriorityQueue is O(n).
    And each element is put into and take out of the PriorityQueue at most once.
    Thus the total time is still O(n).

    public class Solution {
        /**
         * Using a minimum heap to store all the intervals based on the start point. 
         * Take the top element and compare its end time with the start time of next one. 
         * If there exists overlapping, return false. 
         * O(n) time, O(n) space where n is the length of the intervals array. 
         */
        public boolean canAttendMeetings(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) return true;
            
            Queue<Interval> minHeap = new PriorityQueue<>((i1, i2) -> {
                return i1.start - i2.start;
            });
            
            for (Interval i : intervals) {
                minHeap.add(i);
            }
            
            while (!minHeap.isEmpty()) {
                Interval curr = minHeap.poll();
                if (minHeap.peek() != null && curr.end > minHeap.peek().start) {
                    return false;
                }
            }
            
            return true;
        }
    }
    

  • 0
    2

    ur kidding me, this is the same as sorting.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.