首页 > 编程语言 >2023-06-02 练习算法 - TODO

2023-06-02 练习算法 - TODO

时间:2023-06-02 22:22:15浏览次数:56  
标签:02 pq 06 会议室 int points 扫描线 2023 return

练习扫描线算法

视频:基础算法(一) -- 扫描线_哔哩哔哩_bilibili

391 · Number of Airplanes in the Sky - LintCode 【基础】

“这个是扫描线的基础题,后面其他题目都是它的套娃。”

253. 会议室 II - 力扣(LeetCode)【MID】

思路1:扫描线算法,很简单。复杂度分析:O(nlogn),空间: O(n) 【实现非常简单,固定套路】

class Solution {
    public int minMeetingRooms(int[][] A) {
        // swipping line
        List<int[]> points = new ArrayList<>();
        for(int[] a : A) {
            points.add(new int[] {a[0], 1});
            points.add(new int[] {a[1], -1}); // 这里设置-1,方便后续遍历时,直接累加。而不需要判断是开始还是结束
        }
        Collections.sort(points, (x, y) -> {
            if (x[0] != y[0]) return Integer.compare(x[0], y[0]);
            return Integer.compare(x[1], y[1]);
        });

        int ans = 0, count = 0;
        for (int[] point : points) {
            count += point[1];
            ans = Math.max(ans, count);
        }
        return ans;
    }
}

思路2:优先队列。复杂度分析:O(nlogn)

class Solution {
    public int minMeetingRooms(int[][] A) { // 优先队列
        int n = A.length;
        // 对会议按开始时间排序,我们先安排最先开始的会议
        Arrays.sort(A, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        // 记录每个会议室的结束时间
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 对于第一个会议,肯定要分配一间会议室
        pq.offer(A[0][1]);
        for(int i = 1; i < n; i++) {
            // 至于当前的会议A[i] 我需要看,目前分配的会议室是否够用,有没有哪一个已经结束了
            if (A[i][0] >= pq.peek()) { // 可以共用堆顶的这个会议室
                pq.poll();                
            }
            pq.offer(A[i][1]);            
        }
        // 队列中记录了分配的每个会议室,最后一场会议的结束时间
        return pq.size();
    }
}

标签:02,pq,06,会议室,int,points,扫描线,2023,return
From: https://www.cnblogs.com/xianzhon/p/17453016.html

相关文章

  • 2023年6月2日,ArrayList
    1.ArrayListpackagecom.wz.arraylist_class;importjava.util.*;publicclasstest02{/***知识点:集合中可以存储不同类型的元素*泛型*@paramargs**/publicstaticvoidmain(String[]args){ArrayList<String>list......
  • 2023.6.2linux系统文件查找
    03.Linux系统⽂件查找⽂件查找概述find名称查找find⼤⼩查找find时间查找find⽤户查找find类型查找find权限查找find处理动作Authorvx:WingspanGo⽂件查找概述Linux系统中的find命令在查找⽂件时⾮常有⽤⽽且⽅便。它可以根据不同的条件来进⾏查找⽂件:例如⽂件......
  • MISC|[GKCTF 2021]签到
    流量分析题追踪http流量,在tcp.streameq5处发现与flag相关字符从QER1=cat+%2Ff14g%7Cbase64这里可以看出数据是做了base64处理将返回的16进制数据转为字符,再进行base64解码得到以下字符wIDIgACIgACIgAyIK0wIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMyIjMiCNoQDjM......
  • 2023.6.3——软件工程日报
    所花时间(包括上课):6h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习。我了解到的知识点:1.了解了一些数据库的知识;2.了解了一些python的知识;3.了解了一些英语知识;5.了解了一些Javaweb的知识;4.了解了一些数学建模的知识;6.了解了一些计算机网络的知识;......
  • 2023春季学期课程总结
       回顾课程计划:现状、经验、计划:软件工程专业的专业课学习并不算好,基础很差。Java部分增删改查不够熟练,但是也算能勉强写出来。JAVA水平大概就是这样。计划的话,本学期结束时,在专业内部,水平达到中上游水平。学习要借鉴水平高的同学,多学习,用博客记录。  完成程度就专业......
  • 2023-06-02:给定一个二进制数组 nums 和一个整数 k, k位翻转 就是从 nums 中选择一个长
    2023-06-02:给定一个二进制数组nums和一个整数k,k位翻转就是从nums中选择一个长度为k的子数组,同时把子数组中的每一个0都改成1,把子数组中的每一个1都改成0。返回数组中不存在0所需的最小k位翻转次数。如果不可能,则返回-1。子数组是数组的连续部分。输入:nums......
  • [20230531]insert blob数据类型.txt
    [20230531]insertblob数据类型.txt--//链接https://connor-mcdonald.com/2023/05/29/why-i-blog/提供插入blob数据类型的简单方法,测试看看.--//正常插入要先插入一个empty_blob(),然后获得一个定位指针,使用dbms_lob.loadfromfile插入.1.环境:SCOTT@test01p>@ver1PORT_STRING......
  • 0002.有监督学习之k-近邻算法
    一、概述k-近邻算法(k-NearestNeighbouralgorithm),又称为KNN算法,是数据挖掘技术中原理最简单的算法。KNN的工作原理:给定一个已知标签类别的训练数据集,输入没有标签的新数据后,在训练数据集中找到与新数据最邻近的k个实例,如果这k个实例的多数属于某个类别,那么新数据就属于这个类别......
  • 总结20230602
    代码时间(包括上课)2h代码量(行):50行博客数量(篇):1篇相关事项:1、今天上午上的是计算机网络,实验报告的进度微乎其微。2、今天上午的第二节课是概率论,老师带着我们把知识点串了一遍,带着讲了讲卷子。3、今天下午是web考试,考的还可以,还有时间检查了一遍。......
  • 2022,数据科学与数据治理项目全纪录
    大家好,我是独孤风。2022年已过去一半多的时间了。这半年多,我们重点关注了LinkedInDatahub、Atlas等元数据管理工具,了解了他们在数据治理领域的作用。也关注了ApacheGriffin等数据质量工具的使用。但是,在数据工程领域这只是冰山一角,近期lakeFS高级工程师EinatOrr发布一份2022年的......