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

  • -1

    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) {
            while (!minHeap.isEmpty()) {
                Interval curr = minHeap.poll();
                if (minHeap.peek() != null && curr.end > minHeap.peek().start) {
                    return false;
            return true;

  • 0

    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.