loading...

Daily Coding Challenge #13

wingkwong profile image Wing-Kam ・5 min read

About

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!

GitHub logo wingkwong / leetcode

🏆 A Collection of my LeetCode Solutions with Explanations 🏆

GitHub logo wingkwong / hackerrank

🏆 A Collection of my HackerRank Solutions with Explanations 🏆

GitHub logo wingkwong / codeforces

🏆 A Collection of my Codeforces Solutions with Explanations 🏆

GitHub logo wingkwong / atcoder

🏆 A Collection of my AtCoder Solutions with Explanations 🏆

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide