Practice/Atlassian/Leetcode 452. Minimum Number of Arrows to Burst Balloons

Leetcode 452. Minimum Number of Arrows to Burst Balloons

CodingMust

Problem

You are setting up security lasers in a hallway. Each meeting room spans a certain range along the hallway, represented as an interval [start, end] where both endpoints are inclusive. You need to position vertical laser beams at specific positions on the number line such that every meeting room's range contains at least one laser.

Your task is to determine the minimum number of lasers required to cover all meeting rooms.

Requirements

1. Return the minimum number of lasers needed to cover all intervals
2. Each laser at position x covers any interval [start, end] where start ≤ x ≤ end
3. If an interval's start or end point contains a laser, that interval is considered covered
4. The input array is not necessarily sorted

Constraints

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• -2³¹ ≤ start < end ≤ 2³¹ - 1
• Aim for O(n log n) time complexity

Examples

Example 1:

Input: intervals = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: Place one laser at position 6 (covers [10,16], [1,6], [7,12]) and another at position 8 (covers [2,8])

Example 2:

Input: intervals = [[1,2],[3,4],[5,6]] Output: 3 Explanation: No intervals overlap, so each needs its own laser

Example 3:

Input: intervals = [[1,5],[2,5],[3,5],[4,5]] Output: 1 Explanation: All intervals share position 5, so one laser at position 5 covers everything