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

435. 无重叠区间

已解答
中等
相关标签
相关企业
给定一个区间的集合 intervals ，其中 intervals[i] = [start(i), end(i)] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 10(5)
• intervals[i].length == 2
• -5 * 10(4) <= start(i) < end(i) <= 5 * 10(4)

代码

package __greedy

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
   n := len(intervals)
   cnt := 0
   sort.Slice(intervals, func(i, j int) bool {
      if intervals[i][0] == intervals[j][0] {
         return intervals[i][1] < intervals[j][1]
      }
      return intervals[i][0] < intervals[j][0]
   })
   for i := 1; i < n; i++ {
      if intervals[i][0] < intervals[i-1][1] {//有重叠
         cnt++
         if intervals[i][1] > intervals[i-1][1] {//更新到最小区间
            intervals[i][1] = intervals[i-1][1]
         }

      }
   }
   return cnt
}
func max(i, j int) int {
   if i > j {
      return i
   }
   return j
}

763. 划分字母区间

已解答
中等
相关标签
相关企业
提示
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = "ababcbacadefegdehijhklij"输出：[9,7,8]解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

代码

func partitionLabels(s string) []int {
    //找到每个字母的区间
    partition := make([][]int, 0)
    n := len(s)
    for i := 0; i < n; i++ {
        max_pos := 0
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                max_pos = j
            }
        }
        partition = append(partition, []int{i, max(max_pos, i)})
    }
    res := make([]int, 0)
    n = len(partition)
    for i := 1; i < n; i++ {
        if partition[i][0] <= partition[i-1][1] {//重叠
            partition[i][0] = partition[i-1][0]
            partition[i][1] = max(partition[i][1], partition[i-1][1])
        } else {//不重叠，记录
            res = append(res, partition[i-1][1]-partition[i-1][0]+1)
        }
    }
    res = append(res, partition[n-1][1]-partition[n-1][0]+1)
    return res
}

56. 合并区间

已解答
中等
相关标签
相关企业
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10(4)
• intervals[i].length == 2
• 0 <= start(i) <= end(i) <= 10(4)

代码

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0]==intervals[j][0]{
            return intervals[i][1]<intervals[j][1]
        }
        return intervals[i][0]<intervals[j][0]
    })
    n := len(intervals)
    res := make([][]int, 0)
    for i := 1; i < n; i++ {
        if intervals[i][0] <= intervals[i-1][1] {//重叠-》合并
            intervals[i][0] = intervals[i-1][0]
            intervals[i][1] = max(intervals[i-1][1], intervals[i][1])
        } else {//不重叠，记录
            res = append(res, intervals[i-1])
        }
    }
    res = append(res, intervals[n-1])
    return res
}