Описание испытания

На плоской стене, изображающей плоскость XY, приклеены несколько сферических воздушных шаров. Воздушные шары представлены в виде двумерного целочисленного массива points, где points[i] = [xstart, xend] обозначает воздушный шар, чей горизонтальный диаметр простирается от xstart до xend. Вы не знаете точные координаты y воздушных шаров.

Стрелки могут быть направлены вверх прямо вертикально (в положительном направлении Y) из разных точек вдоль оси X. Воздушный шар с xstart и xend лопается от стрелы, выпущенной в x, если xstart <= x <= xend. Количество выпущенных стрел нет ограничений. Выпущенная стрела продолжает бесконечно лететь вверх, разрывая все воздушные шары на своем пути.

Получив массив points, верните минимальное количество стрел, которое нужно пустить, чтобы взорвать все шарики.

Пример 1

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Пример 2

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Пример 3

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Интуиция

Если мы рассмотрим проблемы, связанные с интервалами, первое, что мы сделаем, это отсортируем, но как и по какому столбцу.

Во-первых, посмотрите на интервал, на котором мы можем решить задачу либо по стратегии обратного порядка, либо по возрастанию. Здесь я решаю, используя обратный порядок.

Подход

  1. Отсортируйте точки в соответствии с начальными точками.
  2. Пройдите точки от последних начальных точек и проверьте, заканчивается ли мой последний интервал до интервала curr_start. Если это так, обновите новый интервал curr_start до последней начальной точки интервала и подсчитайте стрелки.
  3. Повторите шаг — 2 для всех точек в массиве точек.
  4. Вернуть количество стрелок.

Сложность

  • Временная сложность:
    O(NlogN)
  • Сложность пространства:
    O(1)
function findMinArrowShots(points: number[][]): number {
  // Sort the points in descending order based on the first coordinate (x) of each point
  points.sort((a, b) => b[0] - a[0]);

  // Initialize the answer with 1 (at least one arrow is needed to start)
  let ans = 1;
  // Initialize the current position with the x-coordinate of the first point
  let currPos = points[0][0];

  // Loop through each point (x, y) in the sorted array
  for (const [x, y] of points) {
    // If the y-coordinate of the current point is less than the current position,
    // it means the current arrow cannot burst this balloon, so we need a new arrow.
    if (y < currPos) {
      // Update the current position with the x-coordinate of the current point
      currPos = x;
      // Increment the answer (a new arrow is needed)
      ans++;
    }
  }

  // Return the minimum number of arrows needed
  return ans;
}