Intervals¶
Table of Contents¶
- 55. Jump Game (Medium)
- 45. Jump Game II (Medium)
- 452. Minimum Number of Arrows to Burst Balloons (Medium)
- 435. Non-overlapping Intervals (Medium)
- 763. Partition Labels (Medium)
- 56. Merge Intervals (Medium)
55. Jump Game¶
"""
- Return `True` if you can reach the last index, otherwise `False`.
"""
from typing import List
# Greedy - Interval
def canJump(nums: List[int]) -> bool:
n = len(nums)
reach = 0
i = 0
while reach >= i:
if reach >= n - 1:
return True
reach = max(reach, i + nums[i])
i += 1
return False
if __name__ == "__main__":
assert canJump([2, 3, 1, 1, 4]) is True
assert canJump([3, 2, 1, 0, 4]) is False
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int canReach = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > canReach) return false;
canReach = max(canReach, i + nums[i]);
}
return true;
}
};
int main() {
Solution obj;
vector<int> nums = {2, 3, 1, 1, 4};
cout << obj.canJump(nums) << endl;
return 0;
}
45. Jump Game II¶
"""
- Return the minimum number of jumps to reach the last index.
"""
from typing import List
# Greedy - Interval
def jump(nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
reach = 0
left, right = 0, 0
res = 0
while right < n - 1:
for i in range(left, right + 1):
reach = max(reach, i + nums[i])
left = right + 1
right = reach
res += 1
return res
if __name__ == "__main__":
assert jump([2, 3, 1, 1, 4]) == 2
assert jump([2, 3, 0, 1, 4]) == 2
452. Minimum Number of Arrows to Burst Balloons¶
from typing import List
class findMinArrowShots:
@staticmethod
def interval_end(points: List[List[int]]) -> int:
n = len(points)
if n <= 1:
return n
points.sort(key=lambda x: x[1])
res = 1
cur = points[0][1]
for i, j in points[1:]:
if i > cur:
res += 1
cur = j
return res
@staticmethod
def interval_start(points: List[List[int]]) -> int:
n = len(points)
if n <= 1:
return n
res = 1
points.sort(key=lambda x: x[0])
for i in range(1, n):
if points[i][0] > points[i - 1][1]:
res += 1
else:
points[i][1] = min(points[i][1], points[i - 1][1])
return res
if __name__ == "__main__":
points = [[10, 16], [2, 8], [1, 6], [7, 12]]
assert findMinArrowShots.interval_end(points) == 2
assert findMinArrowShots.interval_start(points) == 2
435. Non-overlapping Intervals¶
from typing import List
def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
if len(intervals) <= 1:
return 0
intervals.sort(key=lambda x: x[0])
result = 0
for i in range(1, len(intervals)):
if intervals[i][0] >= intervals[i - 1][1]:
continue
else:
result += 1
intervals[i][1] = min(intervals[i][1], intervals[i - 1][1])
return result
print(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]])) # 1
763. Partition Labels¶
from typing import List
# 1. Hashmap
def partitionLabels1(s: str) -> List[int]:
hashmap = {}
for i, j in enumerate(s):
if j not in hashmap:
hashmap[j] = [i, i]
else:
hashmap[j][1] = i
intervals = list(hashmap.values())
intervals.sort(key=lambda x: x[0])
if len(intervals) < 2:
return len(intervals)
res = []
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
intervals[i][1] = max(intervals[i][1], intervals[i - 1][1])
else:
res.append(intervals[i][0])
res.append(intervals[-1][1] + 1)
if len(res) == 1:
return res
else:
for i in range(len(res) - 1, 0, -1):
res[i] -= res[i - 1]
return res
# Single Pass Partitioning
def partitionLabels2(s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
res = []
start, end = 0, 0
for i, c in enumerate(s):
end = max(end, last[c])
if end == i:
res.append(end - start + 1)
start = i + 1
return res
print(partitionLabels1("abaccd")) # [3, 2, 1]
print(partitionLabels2("abaccd")) # [3, 2, 1]
56. Merge Intervals¶
"""
- Merge all overlapping intervals.
<iframe width="560" height="315" src="https://www.youtube.com/embed/44H3cEC2fFM?si=J-Jr_Fg2eDse3-de" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""
from typing import List
# Intervals
def merge(intervals: List[List[int]]) -> List[List[int]]:
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}