Swipe Line

• 時間或空間上的兩個狀態分別儲存

391t. Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

• 建立在空中的時間點(time, flag)並sort

• loop timeline list to check max flight on air

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */
class Point{
    public int time;
    public int flag;
    public Point(int time, int flag){
        this.time = time;
        this.flag = flag;
    }
}

public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        List<Point> timeline = new ArrayList<>();
        for(Interval i: airplanes){
            // 若時間相同，先計算降落的飛機，故擺0
            timeline.add(new Point(i.start, 1));
            timeline.add(new Point(i.end, 0));
        }

        Collections.sort(timeline, (a,b) ->{
            if(a.time == b.time)  return a.flag - b.flag;
            else return a.time - b.time;}
            );

        int max=0;
        int count=0;

        for(Point p: timeline){
            if(p.flag == 1) count++;
            else count--;
            max = Math.max(max, count);
        }
        return max;
    }
}

218 The Skyline Problem

1. 想法：保存一個 maxheap, 在x軸上注意高度變化，有變化就add point

2. Store left edge and right edge, left edge with negative trick

3. Sort it with x linear, then y linear(因為是負的所以先拿到較高的)

4. Travers points, left point 加入heap, left pint remove

5. maxHeap: add left edge, remove right edge, add 0 as the base

6. If height changes, add it to answer

   *Video

public List<int[]> getSkyline(int[][] buildings) {
    // Exceptions:
    //  _______      ________  
    //  |___  |      |    __|
    //  |   | |      |   |  |
    // _|___|_|__   _|___|__|_
    //
    List<int[]> buildingPoints = new ArrayList<>();
    // trick to set negative on left edge
    for (int[] building: buildings){
        buildingPoints.add(new int[] {building[0], -building[2]});
        buildingPoints.add(new int[] {building[1], building[2]});
    }

    Collections.sort(buildingPoints, 
        // because negative hight we got right sorting order
        (a,b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
    );

    List<int[]> ans = new ArrayList<>();
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    // 0 is the compare base
    maxHeap.add(0);
    int preHeight = 0;
    for (int[] point: buildingPoints){
        if (point[1] < 0){
            maxHeap.add(-point[1]);
        }else{
            maxHeap.remove(point[1]);
        }
        int maxHeight = maxHeap.peek();
        if (preHeight != maxHeight){
            ans.add(new int[] {point[0], maxHeight});
            preHeight = maxHeight;
        }
    }
    return ans;
}

Cheapest Price In Time Intervals

Given intervals of time and a lower price for the item during this interval, calculate the cheapest price for the item during the day within different time intervals. Input data is {startTime, endTime, price}. For example: [{0, 4, 5}, {2, 8, 3}, {7, 11, 10}], the result should be [{0, 2, 5}, {2, 8, 3}, {8, 11, 10}]”

• Decouple input to entry and exit points

• Maintain minHeap as available heights in current point

• Update result whenever a hight change and modify the end time in pre interval

• Compare to 1235. Maximum profit in job scheduling

from functools import cmp_to_key
from heapq import *

def solution(arr):
  li = []
  for x in arr:
    li.append((x[0], -x[2]))
    li.append((x[1], x[2]))

  li.sort(key = cmp_to_key(lambda a, b: a[0] - b[0] \
    if a[0] != b[0] else a[1] - b[1]))

  res = [[0, 0, 0]]
  minHeap = [float('inf')]
  preLow = 0

  for ele in li:
    if ele[1] < 0:
      heappush(minHeap, -ele[1])

    else:
      minHeap.remove(ele[1])
      heapify(minHeap)
    
    lowest = minHeap[0]

    if lowest != preLow:
      res[-1][1] = ele[0]
      preLow = lowest
      res.append([ele[0], ele[0], lowest])

  return res[1:-1]

test = [[0, 4, 5], [2, 8, 3], [7, 11, 10]]
print(solution(test))