草庐IT

leetcode 435. Non-overlapping Intervals 无重叠区间(中等)

okokabcd 2023-03-28 原文

一、题目大意

标签: 贪心

https://leetcode.cn/problems/non-overlapping-intervals

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 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 <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

二、解题思路

求最小的移除区间个数，等价于尽量多保留不重叠的区间。在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此我们采取的贪心策略为：优先保留结尾小且不相交的区间。
具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。
输入数组区间为[[1, 2], [2, 4], [1, 3]]，排序后的数组为[[1, 2], [1, 3], [2, 4]]。按照贪心策略，首先初始化为区间[1, 2]，由于[1, 2]与[1, 3]相交，我们跳过该区间；由于[2, 4]与[1, 2]不相交，我们将其保留，因此最终保留的区间为[[1, 2], [2, 4]]。

三、解题方法

3.1 Java实现

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        int n = intervals.length;
        // 二维数组排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int removed = 0;
        int prev = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] < prev) {
                removed++;
            } else {
                prev = intervals[i][1];
            }
        }
        return removed;
    }
}

四、总结小记

  • 2022/7/14 赶紧把wps卸载了
无重Non-overlappingintervalsstrongblockquote算法与数据结构

有关leetcode 435. Non-overlapping Intervals 无重叠区间(中等)的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  3. ruby-on-rails - ruby rails : Unit Testing non activerecord models and still load fixtures - 2

    我可能遗漏了一些东西，但我陷入了这种情况:我有一个非activerecord模型，我想对其进行测试。我从Test::Unit::TestCase派生了它的测试用例类。但是，模型的测试用例类在其自身内部使用了其他activerecord模型类，我想为它们加载固定装置。我的问题是fixtures类方法仅在我从ActiveSupport::TestCase继承测试用例类时才可用(它在ActiveRecord::TestFixtures包含在ActiveSupport::TestCase中)。任何帮助，因为运行测试都会给我错误:未定义的方法“fixtures”(这是可以理解的)，如果我从Act

  4. ruby - 错误 "non-absolute home"通过网络 :SSH - 2

    有问题的代码Net::SSH.start('servername','user')这将返回“非绝对主页”。“用户”实际上有一个主目录。一种建议的方法是使用IdentityFile的完整路径修改~/.ssh/config。这并没有解决问题。其中最疯狂的部分是，如果通过irb或控制台调用，代码可以正常工作。当我们尝试从类方法(使用相同的代码)中调用它时，它会返回“非绝对主页”错误。“用户”也可以通过命令行ssh进入服务器而不会出现问题。服务器正在运行Ubuntu。更新感谢@Phrogz-解决方法是将ENV['HOME']设置为'/home/deploy'。但是，我还没有弄清楚为什么$HOM

  5. ruby-on-rails - Rails 和 attr_accessible : is there a way to raise an exception if a non-mass-assignable attribute is mass-assigned? - 2

    如果尝试批量分配attr_accessible不允许的属性，是否有办法让Rails引发错误？这在开发中会很方便，可以提醒我为什么我Shiny的新模型不起作用，也有助于登录生产环境以检测恶意事件。我正在使用Rails2.3.8，但可能很快就会迁移到3。 最佳答案 从Rails3.2开始，这不再需要monkeypatching——rails现在提供了这种行为。将其放入development.rb和test.rb:config.active_record.mass_assignment_sanitizer=:strict

  6. ruby-on-rails - 弃用警告 : Dangerous query method (method whose arguments are used as raw SQL) called with non-attribute argument(s) - 2

    我将我的Rails5.1.4应用更新到了5.2.0。我的一个模型中有以下范围:scope:by_category,lambda{|category_slug|category_ids=Category.find_by(slug:category_slug)&.subtree_idswhere(category_id:category_ids)}由于该范围，Rails返回以下错误:DEPRECATIONWARNING:Dangerousquerymethod(methodwhoseargumentsareusedasrawSQL)calledwithnon-attributeargume

  7. ruby - 表示 "at least one non-digit"的正则表达式 - 2

    我想根据这个模式验证用户名:允许的字符:字母、数字、连字符、下划线第一个字符必须是字母或数字用户名不能全是数字这个正则表达式满足上面的1和2，但是我想不通如何满足3:/^[a-zA-Z\d][\w\-]+$/(我正在使用Ruby，如果相关的话) 最佳答案 不是很高效，但是很简单:/^(?!\d+$)[a-zA-Z\d][\w\-]+$/前瞻只是意味着:“后面不是一串数字，一直持续到最后”。 关于ruby-表示"atleastonenon-digit"的正则表达式，我们在StackOver

  8. ruby-on-rails - 重定向到某个页面而不是 :notice when non-confirmed user logs in - 2

    如何将登录到特定页面的未确认用户重定向到某个页面而不是显示:notice(“您必须确认您的帐户”)。使用Devisegem(最新)这个问题:(Devise-Redirectedtopageifaccountisn'tconfirmed)提供了这个解决方案:#config/initializers/my_strategy.rbWarden::Strategies.add(:my_strategy)dodefvalid?trueenddefauthenticate!u=User.find_for_authentication(:email=>params[:email])ifu.nil?|

  9. Ruby 并发 : non-blocking I/O vs threads - 2

    我正在研究Ruby(1.9.3-p0)中的并发性，并创建了一个非常简单的I/O密集型代理任务。首先，我尝试了非阻塞方法:require'rack'require'rack/fiber_pool'require'em-http'require'em-synchrony'require'em-synchrony/em-http'proxy=lambda{|*|result=EM::Synchrony.syncEventMachine::HttpRequest.new('http://google.com').get[200,{},[result.response]]}useRack::Fi

  10. 工程（十一）——NUC11+D435i+VINS-FUSION+ESDF建图（github代码） - 2

    博主的合并代码git@github.com:huashu996/VINS-FUSION-ESDFmap.git一、D435i深度相机配置1.1SDK+ROS参考我之前的博客，步骤和所遇见的问题已经写的很详细了https://blog.csdn.net/HUASHUDEYANJING/article/details/129323834?spm=1001.2014.3001.55011.2相机标定参数1、相机内参通过rostopic的camera/info获取header：标准消息头seq：序列ID，连续递增的ID号stamp：两个时间戳frame_id：与此数据相关联的帧IDheight：图像尺

随机推荐