# Daily Coding Challenge #13

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature
*/

class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> ans;
// like merge sort. use two pointers to combine the sorted sequences
for(int i=0,j=0;i<A.size()&&j<B.size();A[i][1]<B[j][1]?i++:j++){
int start=max(A[i][0],B[j][0]);
int end=min(A[i][1],B[j][1]);
if(start<=end) ans.push_back({start,end});
}
return ans;
}
};
``````

``````/*
LeetCode - Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
*/

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans;
// if no interval, return empty vector<vector<int>>{}
if(intervals.size()==0) return ans;
// sort the interval by start time
sort(intervals.begin(),intervals.end(),[](vector<int>& a, vector<int>&b){
return a[0]<b[0];
});
// put the first ans
ans.push_back(intervals[0]);
// traverse the rest of them
for(int i=1;i<intervals.size();i++){
if(ans.back()[1]<intervals[i][0]){
// if the current end time is less than the start time of the next one
// i.e. not overlap
// e.g. [[1,2],[4,5]]
// then push back intervals[i]
ans.push_back(intervals[i]);
} else {
// if it is overlapping
// e.g. [[1,3],[2,6]]
// since [1,3] is already in ans
// modify the end time in the last element of ans
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
}
}
return ans;
}
};
``````

``````/*
LeetCode - Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:

Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:

Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
*/

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
// similar to 56 - Merge Intervals
int ans=0;
if(intervals.size()==0) return ans;
sort(intervals.begin(),intervals.end(),[](vector<int>& a,vector<int>& b){
return a[0]<b[0];
});
for(int i=1,j=0;i<intervals.size();i++){
// check if they are overlapping
if(intervals[i][0]<intervals[j][1]){
// if so, add 1 to ans
ans++;
// if the end time of intervals[j] is greater than that of intervals[i]
// intervals[j] should be removed
// so we update j
if(intervals[j][1]>intervals[i][1]){
// [[1,100],[11,22],[1,11],[2,12]]
j=i;
}
} else{
// update j for the next check
j=i;
}
}
return ans;
}
};
``````

``````/*
LeetCode - Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
*/

class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int ans=0;
long t=LONG_MIN;
if(points.size()==0) return ans;
sort(points.begin(),points.end(),[](vector<int>& a, vector<int>& b){
// sort by the end point
return a[1]<b[1];
});
// traverse each point
for(int i=0;i<points.size();i++){
if(t<points[i][0]){
// if the previous end point is less than current start point
// that means a new non-overlapping interval is found
// update t and add 1 to ans
t=points[i][1];
ans++;
}
}
return ans;
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.