- 浏览: 173228 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
题目中给定了一个排好序的interval数组,interval之间没有覆盖,然后插入一个新的interval,merge之后返回,从第一个元素开始,如果有冲突更新newInterval的start,将它加入结果集中,然后判断newInterval的end属性。遍历一遍数组,时间复杂度为O(n)。代码如下:
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
题目中给定了一个排好序的interval数组,interval之间没有覆盖,然后插入一个新的interval,merge之后返回,从第一个元素开始,如果有冲突更新newInterval的start,将它加入结果集中,然后判断newInterval的end属性。遍历一遍数组,时间复杂度为O(n)。代码如下:
/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { List<Interval> list = new ArrayList<Interval>(); if(intervals == null || intervals.size() == 0) { list.add(newInterval); return list; } int i = 0; while(i < intervals.size() && intervals.get(i).end < newInterval.start) { list.add(intervals.get(i)); i ++; } if(i < intervals.size()) newInterval.start = Math.min(newInterval.start, intervals.get(i).start); list.add(newInterval); while(i < intervals.size() && newInterval.end >= intervals.get(i).start) { newInterval.end = Math.max(newInterval.end, intervals.get(i).end); i ++; } while (i < intervals.size()) { list.add(intervals.get(i)); i ++; } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
12 Insert Interval 45 13 Two Sum 47 14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design 51 16 3Sum 53 17 4Sum 55 18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge ...
Insert Interval Merge Intervals Minimum Window Substring Multiply Strings Substring with Concatenation of All Words Pascal's Triangle Pascal's Triangle II Spiral Matrix Spiral Matrix II ZigZag ...
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 ...Insert Interval Easy Two Strings Are Anagrams(比较字符串) E
Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解。 2018-08-19 19:16 LeetCode: 79. Word Search 解决方法:DFS LeetCode: 31...
LifeInterval57Insert Interval56Merge Intervals252Meeting Rooms253Meeting客房II352Data流从数据Stream53Maximum Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数...
INSERT INTO warranty VALUES 123 INTERVAL "8" MONTH ; INSERT INTO warranty VALUES 155 INTERVAL "200" YEAR 3 ; INSERT INTO warranty VALUES 678 "200 11" ; SELECT FROM ...
3 insert into TEST values(sysdate); 4 end; 5 / 过程已创建。 创建JOB SQL> variable job1 number; SQL> SQL> begin 2 dbms_job.submit(:job1,'MYPROC;',sysdate,'sysdate+1/...
ep_insert 时间戳功能当用户triggerSequence中定义的字符串时,插入当前的 UNIX 时间戳。 实现了一个非常简单的时间偏移校正,每updateInterval毫秒触发一次。 如果 Starttime 定义为Starttime: YYYY-MM-DD HH:MM:SS...
2 learn to file save and open, the interval of print preview, paragraphs, the first character position change, etc., can insert images, forms, art words in the Word, special symbols, etc. (3) ...
python-mysql-parrot-analytics ETL管道从API和INSERT INTO Mysql DB调用Parrot Analytics每月需求数据使用configuration.py来配置设置START_DATE ='2020-01-01'->数据查询的开始日期END_DATE ='2020-12-31'->数据...
'sysdate + 15/1440'–interval,设置定时器执行的频率,这样写每隔15分钟执行一次 ); commit; end; 这里第一个参数是任务编号,系统自动赋值。也可以采用isubmit来手动指定 第二个参数是需要执行...
this.timer3.Interval = 100; this.timer3.Start(); } else { SqlCommand sqlcmd; String sql = "insert into COM_JS_DATA values (" + comID.ToString() + ",getdate(),'" + STR + "')"; sqlcmd = new ...
-Interval [ms] 定时欺骗的时间间隔,默认是3秒 -spoofmode [1|2|3] 将数据骗发到本机,欺骗对象:1为网关,2为目标机,3为两者 -speed [kb] 限制指定的IP或IP段的网络总带宽,单位:KB example: 嗅探指定的IP段中端口...
5)蛇身移动的实现:蛇身的移动主要是用ArrList类来实现的,该类的主要功能是使用大小可以根据需要动态增加数组,即建立动态数组来存储蛇身,本实验主要使用ArrList类的Insert方法和RemoveAt方法实现蛇模块的增加、...
一、单项选择题 (只有一个正确答案) 【1】 执行语句"SELECT '2008-01-20'+ INTERVAL 2 DAY; "结果为 A: 2008-01-22 B: 2010-01-20 C: 2008-02-11 D: 2008-03-20 答案: A 【2】 下列哪个是不正确的MySQL的变量命名...
― Number(p, s) Oracle 主要数据类型 4-3 Date 数据类型 ―Date ―Timestamp ―Interval day to second ―Interval year to month ―Timestamp with time zone ―Timestamp with local time zone Oracle 主要数据...
― Number(p, s) Oracle 主要数据类型 4-3 Date 数据类型 ―Date ―Timestamp ―Interval day to second ―Interval year to month ―Timestamp with time zone ―Timestamp with local time zone Oracle 主要数据...
insert into temp values(null, ‘jack’, 22), (null, ‘jackson’ 23); 2、 update 修改语句 update主要完成对数据的修改操作,可以修改一条或多条数据。修改多条或指定条件的数据,需要用where条件来完成。 ...
SqlCommand sqlcom = new SqlCommand("insert into oa_smsend( Mobile,Content) values('" + phone + "','" + verify + "') ", this.my_sql_con); sqlcom.ExecuteNonQuery(); last_id = id; my_sql_con.Close();...