Categories
LeetCode

LeetCode 57. Insert Interval [sort] Java

Source URL:https://leetcode.com/problems/insert-interval/

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:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

This problem is very familiar with problem 56. So we use the easiest way, we just use the code of problem 56. We can just put the new interval to the end of the intervals array. Then we call the merge function from problem 56.

Running time is 3ms only faster than 24.68% Java submissions, I think it is acceptable. If we want to solve this problem carefully, I think we need to find the first overlapping interval, then try to merge it and the next one, until there is no overlapping interval left. It is not very hard and maybe faster than the current solution.

Github address:https://github.com/tinyfool/leetcode/tree/master/src/p0057

To find other sort problems, see also Sort algorithms and problems.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.