# 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

```java
/**
 * 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](https://leetcode.com/problems/the-skyline-problem/description/)

1. 想法：保存一個 maxheap, 在x軸上注意高度變化，有變化就add point&#x20;
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](https://www.youtube.com/watch?v=11dq8ux25oE\&t=1513s)

```java
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](https://app.gitbook.com/@netjimmy/s/code-interview-note/~/drafts/-MBSOXq06oc0RkbY7zA6/dynamic/general#1235-maximum-profit-in-job-scheduling)

```python
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))
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/array/swipe-line.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.