class Solution {
    public boolean genericTemplate(int[][] intervals) {
        if(intervals.length==0) //validation check
            return true;
        Arrays.sort(intervals, (a,b)->Integer.compare(a[0],b[0]); //sort by start times
        int[] prev = intervals[0]; //keep a pointer to the previous interval;
        //iterate through rest of the intervals and check overlap between intervals
        for(int i=1;i<intervals.length;i++) {         
            int[] current = intervals[i];
            if(doIntervalsOverlap(prev, current)){
                // if overlap Do business logic
            }
            prev = current; //move the prev pointer
        }
        return $result; //return result
    }
    
    private boolean doIntervalsOverlap(int[] i1, int[] i2) {
        //if the start of the second interval is greater or equal than the end of the first interval they dont overlap
        // > or >= depends on the exact problem
        // for example in some cases [4,6] [6,10] are considered overlapping, in some not
        if(i2[0]>=i1[1]) 
            return false;
        return true;
    }
}

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if(intervals==null || intervals.length==0)
            return true;
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);
        int[] prev = intervals[0];
        for(int i=1;i<intervals.length;i++) {
            int[] current = intervals[i];
            if(doIntervalsOverlap(prev, current)){
                return false;
            }
            prev = current;
        }
        return true;
    }
    
    private boolean doIntervalsOverlap(int[] i1, int[] i2) {
        if(i2[0]>=i1[1]) //if the start of the second interval is greater or equal than the end of the first interval they dont overlap
            return false;
        return true;
    }
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
         if(intervals==null || intervals.length==0)
            return 0;
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1]-b[1]);
        minHeap.offer(intervals[0]);
        for(int i=1;i<intervals.length;i++) {
            int[] prev = minHeap.poll();
            int[] curr = intervals[i];
            if(areMeetingsOverlapping(prev, curr)){
                //if the meetings overlap we ll need a new room
                minHeap.offer(curr);
            } else {
                //if not we just merge the interval
               prev[1] = Math.max(prev[1], curr[1]);
            }
            //put the meeting back
            minHeap.offer(prev);
        }
        
        return minHeap.size();
    }
    
        private boolean areMeetingsOverlapping(int[] i1, int[] i2) {
        if(i2[0]>=i1[1]) //if the start of the second interval is greater or equal than the end of the first interval they dont overlap
            return false;
        return true;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length==0)
            return intervals;
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);
        List<int[]> mergedList = new ArrayList<>();
        int[] prev = intervals[0];
        for(int i=1;i<intervals.length;i++) {
            int[] curr = intervals[i];
            if(doIntervalsOverlap(prev, curr)) {
               prev[1] = Math.max(prev[1], curr[1]);
            } else {
                mergedList.add(prev);
                prev = curr;
            }
        }
        mergedList.add(prev);
        return convertListToArray(mergedList);
    }
    
    private boolean doIntervalsOverlap(int[] i1, int[] i2) {
        if(i2[0]>i1[1])
            return false;
        return true;
    }
    
    private int[][] convertListToArray(List<int[]> mergedList) {
        int[][] result = new int[mergedList.size()][2];
        for(int i=0;i<mergedList.size();i++) {
            result[i] = mergedList.get(i);
        }
        return result;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals==null || intervals.length==0)
            return 0;
        Arrays.sort(intervals, (a,b) -> a[0]-b[0]);
        int count = 0;
        int[] prev = intervals[0];
        for(int i=1;i<intervals.length;i++) {
            if(areIntervalsOverlapping(prev, intervals[i])) {
                count++;
                if(prev[1]>=intervals[i][1]) {
                    prev = intervals[i];
                }
            } else {
                prev = intervals[i];
            }
        }
        return count;
    }
    
    private boolean areIntervalsOverlapping(int[] i1, int[] i2) {
        if(i2[0]>=i1[1])
            return false;
        return true;
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points==null || points.length==0)
            return 0;
        Arrays.sort(points, (a,b) -> a[1]-b[1]);
        int[] prev = points[0];
        int arrows =1;
        for(int i=1;i<points.length;i++){
            int[] curr = points[i];
            if(!areBallonsOverlapping(prev, curr)) {
                arrows++;
                prev = curr;
            }
            
        }
        return arrows;
    }
    
    private boolean areBallonsOverlapping(int[] i1, int[] i2) {
        if(i2[0]>i1[1])
            return false;
        return true;
    }
}