Leetcode1109. 航班预订统计

2024-02-01 07:04

本文主要是介绍Leetcode1109. 航班预订统计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Every day a Leetcode

题目来源:1109. 航班预订统计

解法1:差分数组

注意到一个预订记录实际上代表了一个区间的增量。我们的任务是将这些增量叠加得到答案。因此,我们可以使用差分解决本题。

在这里插入图片描述

代码:

/** @lc app=leetcode.cn id=1109 lang=cpp** [1109] 航班预订统计*/// @lc code=start// 差分数组class Solution
{
public:vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n){// 构造差分数组vector<int> diff(n + 1, 0);for (vector<int> &booking : bookings){int first = booking[0];int last = booking[1];int seats = booking[2];diff[first - 1] += seats;diff[last] -= seats;}int sum = 0;vector<int> ans;for (int i = 0; i < n; i++){sum += diff[i];ans.push_back(sum);}return ans;}
};
// @lc code=end

结果:

在这里插入图片描述

复杂度分析:

时间复杂度:O(n+m),其中 n 是航班数,m 是数组 bookings 的元素个数。

空间复杂度:O(n),其中 n 是航班数。

这篇关于Leetcode1109. 航班预订统计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/666450

相关文章

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量

如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

《如何使用Bash脚本中的time命令来统计命令执行时间(中英双语)》本文介绍了如何在Bash脚本中使用`time`命令来测量命令执行时间,包括`real`、`user`和`sys`三个时间指标,... 使用 Bash 脚本中的 time 命令来统计命令执行时间在日常的开发和运维过程中,性能监控和优化是不

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

Python脚本:TXT文档行数统计

count = 0 #计数变量file_dirs = input('请输入您要统计的文件根路径:')filename = open(file_dirs,'r') #以只读方式打开文件file_contents = filename.read() #读取文档内容到file_contentsfor file_content in file_contents: