Two different ways in Java with detailed explanation


  • 0
    L

    I could think of two different ways. One is fairly simple where you could compare two intervals to validate if there is a conflict. The idea is that if there are two intervals, the conflict may happen only if :
    interval1: [0,5]
    interval2:[3,10]
    min(5,10)-max(0,3)>0
    So if you generalize this, it becomes: min(i1.end,i2.end) - max(i1.start,i2.start)>0 for having a conflict.
    The only catch is that you would need to sort the array so that you could compare two elements and move on. Here is the implementation:

    private boolean arraytraversal(Interval[] intervals) {
            Arrays.sort(intervals,(i,j)->Integer.compare(i.start,j.start));
            for(int i=1;i<intervals.length;i++) {
                if(Math.min(intervals[i].end,intervals[i-1].end) - Math.max(intervals[i].start,intervals[i-1].start)>0) {
                    return false;
                }
            }
            return true;
        }
    

    Another way is to add a space of O(n) and use a min heap. Break each interval into start and end times with a meeting object. If there are Make sure that you sort it in a way that the start time comes before the end time. Here is the implementation.

        private boolean minheap(Interval[] intervals) {
            PriorityQueue<Meeting> heap = new PriorityQueue<>((i,j)->{
                int ret = Integer.compare(i.time,j.time);
                if(ret==0) {
                    return i.start?1:-1;
                }
                return ret;});
            for(Interval i : intervals) {
                heap.add(new Meeting(i.start,true));
                heap.add(new Meeting(i.end,false));
            }
            
            int count = 0;
            while(!heap.isEmpty()) {
                Meeting m = heap.poll();
                if(m.start) {
                    count++;
                }
                else {
                    count--;
                }
                if(count>1) {
                    return false;
                }
            }
            return true;
        }
        
        private static class Meeting {
            private int time;
            private boolean start;
            Meeting(int time, boolean start) {
                this.start = start;
                this.time = time;
            }
        }
    

Log in to reply
 

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