Merge Intervals¶
Table of Contents¶
- 56. Merge Intervals (Medium)
- 57. Insert Interval (Medium)
- 55. Jump Game (Medium)
- 763. Partition Labels (Medium)
- 3169. Count Days Without Meetings (Medium)
- 2580. Count Ways to Group Overlapping Ranges (Medium)
- 3394. Check if Grid can be Cut into Sections (Medium)
- 2963. Count the Number of Good Partitions (Hard)
- 2584. Split the Array to Make Coprime Products (Hard)
- 616. Add Bold Tag in String (Medium) 👑
- 758. Bold Words in String (Medium) 👑
- 3323. Minimize Connected Groups by Inserting Interval (Medium) 👑
- 759. Employee Free Time (Hard) 👑
- 2655. Find Maximal Uncovered Ranges (Medium) 👑
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;
}
57. Insert Interval¶
from typing import List
# Interval
def insert(
intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
n = len(intervals)
if n == 0:
return [newInterval]
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
i = 0
result = []
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < n:
result.append(intervals[i])
i += 1
return result
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
print(insert(intervals, newInterval)) # [[1, 5], [6, 9]]
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;
}
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]