Session 34: Heap2

Original Session

Date: 23 Jan 2025

Topic: Heaps2

Concept: Merge intervals.

Concept: Median, middle value in set of data.

Programs

1. 56. Merge Intervals
   1. leetcode here

   public int[][] merge(int[][] intervals) {
           
           Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
           List<int[]> ans = new ArrayList();
           int[] temp = intervals[0];
   
           for (int i=1; i<intervals.length; i++) {
   
               if (intervals[i][0] <= temp[1]) {
                   temp[1] = Math.max(temp[1], intervals[i][1]);
               } else {
                   ans.add(temp);
                   temp = intervals[i];
               }
           }
           ans.add(temp);
           return ans.toArray(new int[ans.size()][2]);
       }

2. 252. Meeting Rooms
   1. leetcode premium here
      1. Question:
         Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
         
         Case 1:
         input: [[0,30],[5,10],[15,20]] Output: false
         
         Case 2:
         input: [[7,10],[2,4]] Output: true
         
         

   public boolean canAttendAllMeetings(int[][] intervals) {
           
           Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
           int[] temp = intervals[0];
   
           for (int i=1; i<intervals.length; i++) {
   
               if (intervals[i][0] <= temp[1]) {
                   return false;
               } else {
                   temp = intervals[i];
               }
           }
           return true;
       }

3. Minimum Platforms
   1. GFG here

   int findPlatform(int arr[], int dep[]) {
           // add your code here
           
           int n = arr.length;
           Arrays.sort(arr);
           Arrays.sort(dep);
           
           int start = 0, end = 0, platform = 0, ans = 0;
           
           while (start < n && end < n) {
               
               if (arr[start] <= dep[end]) {
                   
                   platform ++;
                   start ++;
               } else {
                   
                   platform --;
                   end ++;
               }
               
               if (platform > ans) {
                   ans = platform;
               }
           }
           
           return ans;
       }

4. 295. Find Median from Data Stream
   1. leetcode here
   2. Rules
      1. If MaxHeap is empty them add in maxHeap
      2. If Incoming Value is Smaller than top of the Max Heap → Push to Max Heap.
      3. MaxHeapSize - MinHeapSize ≤ 1
      4. MaxHeapSize will always ≥ MinHeapSize

   class MedianFinder {
   
       PriorityQueue<Integer> minHeap = new PriorityQueue();
       PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());
   
       public MedianFinder() {
           
       }
       
       public void addNum(int num) {
           
           if (maxHeap.isEmpty()) {
               maxHeap.add(num);
           } else if (num <= maxHeap.peek()) {
               maxHeap.add(num);
           } else {
               minHeap.add(num);
           }
   
           if (maxHeap.size() - minHeap.size() > 1) {
               minHeap.add(maxHeap.poll());
           } else if (minHeap.size() > maxHeap.size()) {
               maxHeap.add(minHeap.poll());
           }
   
       }
       
       public double findMedian() {
           
           if (maxHeap.size() == minHeap.size()) {
               return (maxHeap.peek() + minHeap.peek()) / 2d;
           }
   
           return maxHeap.peek();
       }
   }