创作目的：为了方便自己后续复习重点，以及养成写博客的习惯。
一、无重叠区间
思路：参考carl文档
按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
ledcode题目：https://leetcode.cn/problems/non-overlapping-intervals/description/
AC代码：
int cmp(int** a, int** b) {return (*a)[1] - (*b)[1];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {if (intervalsSize == 0) {return 0;}qsort(intervals, intervalsSize, sizeof(int*), cmp);int right = intervals[0][1];int ans = 1;for (int i = 1; i < intervalsSize; ++i) {if (intervals[i][0] >= right) {++ans;right = intervals[i][1];}}return intervalsSize - ans;
}
二、划分字母区间
思路：参考carl文档
统计每一个字符最后出现的位置，从头遍历字符，并更新字符的最远出现下标。如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
lecode题目：https://leetcode.cn/problems/partition-labels/description/
AC代码：
int* partitionLabels(char* s, int* returnSize) {int last[26];int length = strlen(s);for (int i = 0; i < length; i++) {last[s[i] - 'a'] = i;}int* partition = (int*)malloc(sizeof(int) * length);int start = 0, end = 0;*returnSize = 0;for (int i = 0; i < length; i++) {end = fmax(end, last[s[i] - 'a']);if (i == end) {partition[(*returnSize)++] = end - start + 1;start = end + 1;}}return partition;
}三、合并区间
思路：参考carl文档
按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。合并区间后左边界和右边界，作为一个新的区间，加入到result数组里。如果没有合并就把原区间加入到result数组。
ledcode题目：https://leetcode.cn/problems/merge-intervals/description/
AC代码：
int cmp(const void* a, const void* b){return (*(int**)a)[0] > (*(int**)b)[0] ? 1 : -1;
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){if (intervals == NULL || intervalsSize == 0) {return NULL;}qsort(intervals, intervalsSize, sizeof(int*), cmp);int right = intervals[0][1];int** res = (int**)calloc(intervalsSize, sizeof(int*));* returnColumnSizes = (int*)calloc(intervalsSize, sizeof(int));for (int i = 0; i < intervalsSize; i++) {res[i] = (int*)calloc(2, sizeof(int));(* returnColumnSizes)[i] = 2;}*returnSize = 0;res[*returnSize][0] = intervals[0][0];res[*returnSize][1] = intervals[0][1];(* returnSize)++;for (int i = 1; i < intervalsSize; i++) {if (intervals[i][0] > right) {res[*returnSize][0] = intervals[i][0];res[*returnSize][1] = intervals[i][1];right = intervals[i][1];(* returnSize)++; }else if (intervals[i][1] > right){res[*returnSize - 1][1] = intervals[i][1];right = intervals[i][1];}}return res;
}
