代码随想录算法训练营Day36 | 435.无重叠区间、763.划分字母区间、56.合并区间

435.无重叠区间

这题需要判断好两个点：

1、什么时候移除元素？（如何判断重叠？）——当前区间左边界小于之前区间右边界时移除元素

2、移除哪个元素？——移除右边界更靠后的元素

整体解题框架和昨天打气球差不多，也是先排序后处理好右边界

class cmp {
public:
	bool operator()(const vector<int>& v1, const vector<int>& v2) {
		if (v1[0] != v2[0])
			return v1[0] < v2[0];
		else
			return v1[1] > v2[1];
	}
};

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
	std::sort(intervals.begin(), intervals.end(), cmp());

	int ans = 0;
	int right = intervals[0][1];
	for (int i = 1; i < intervals.size(); ++i) {
		if (intervals[i][0] < right) {
			// 如果发生重叠，删除右边界更大的那个（无论删除哪个，剩余的那个左边界都满足不重叠）
			right = std::min(right, intervals[i][1]);
			++ans;
		}
		else {
			right = intervals[i][1];
		}
	}
	return ans;
}

---

763.划分字母区间

这题自己的思路也是将其抽象为昨天打气球类似的框架，写出来虽然能AC但又抽象又繁琐，不是很美丽

大致思路：将每个字母都抽象为一个区间，区间记录其第一次与最后一次出现的位置。之后对这些区间进行排序，逐个将重叠的区间进行合并

（将所有字母抽象为区间后就和后面的56合并区间几乎完全一致了，仅有记录结果的方法不同）

class cmp {
public:
	bool operator()(const vector<int>& v1, const vector<int>& v2) {
		if (v1[0] != v2[0])
			return v1[0] < v2[0];
		else
			return v1[1] > v2[1];
	}
};

vector<int> partitionLabels(string s) {
	// 先统计各个字母出现的左右区间，将问题抽象为重叠区间问题
	vector<vector<int>> letters = { 26, vector<int>{-1, -1} };
	for (int i = 0; i < s.size(); ++i) {
		int ind = s[i] - 'a';
		if (letters[ind][0] == -1) {
			letters[ind][0] = i + 1;
			letters[ind][1] = i + 1;
		}
		else {
			letters[ind][1] = i + 1;
		}
	}
	// 删除没出现过的字母
	for (int i = 0; i < letters.size(); ) {
		if (letters[i][0] == -1)
			letters.erase(letters.begin() + i);
		else
			++i;
	}

	std::sort(letters.begin(), letters.end(), cmp());

	vector<int> ans;
	int right = letters[0][1];
	int sum = 0;		// sum记录之前已经完成分割的字符串长度
	for (int i = 1; i < letters.size(); ++i) {
		// 未重叠时分割字符串
		if (letters[i][0] >= right) {
			ans.push_back(right - sum);
			sum += ans.back();
			right = letters[i][1];
		}
		// 重叠时扩展当前分割的右边界
		else {
			right = std::max(right, letters[i][1]);
		}
	}
	if(sum != s.size())
		ans.push_back(s.size() - sum);
	return ans;
}

实际上只需要统计字母出现的右边界即可
整体思路有点类似于之前的跳跃游戏II：不断更新当前分割下所能到达的最远右边界，当到达右边界时更新结果

vector<int> partitionLabels(string s) {
	// 只统计每个字母的有边界
	int hash[27] = { 0 };
	for (int i = 0; i < s.size(); ++i)
		hash[s[i] - 'a'] = i;

	vector<int> ans;
	// 当前分割的左右边界
	int left = 0;
	int right = 0;
	for (int i = 0; i < s.size(); ++i) {
		// 不断扩张当前分割的右边界
		right = std::max(right, hash[s[i] - 'a']);
		// 如果到达当前分割的右边界，则保存当前分割结果
		if (i == right) {
			ans.push_back(right - left + 1);
			left = i + 1;
			right = i + 1;
		}
	}
	return ans;
}

---

56.合并区间

（按自己的思路写完上面的划分字母区间后再看这题甚至没看出区别）

整体思路与昨天的打气球类似：排序后逐个处理右边界。如果发生重叠则更新当前区间的右边界，如果没重叠则记录结果。

class cmp {
public:
	bool operator()(const vector<int>& v1, const vector<int>& v2) {
		if (v1[0] != v2[0])
			return v1[0] < v2[0];
		else
			return v1[1] > v2[1];
	}
};

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	std::sort(intervals.begin(), intervals.end(), cmp());

	vector<vector<int>> ans;
	int left = intervals[0][0];
	int right = intervals[0][1];
	for (int i = 1; i < intervals.size(); ++i) {
		// 如果重叠则后推右边界（相当于进行了合并）
		if (intervals[i][0] <= right)
			right = std::max(right, intervals[i][1]);
		// 未重叠则记录区间
		else {
			ans.push_back({ left, right });
			left = intervals[i][0];
			right = intervals[i][1];
		}
	}
	ans.push_back({ left, right });
	return ans;
}

---

理解好了昨天的打气球今天的三道题思路其实都差不多（总算有几题能自己做出来了T^T）