loading...

Daily Coding Challenge #24

wingkwong profile image Wing-Kam ・3 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 - Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:

1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000
*/

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        // sort by the diff 
        // ------------------------------------------
        // [[10,20],[30,200],[400,50],[30,20]]
        // -10, -170, 350, 10
        // -170, -10, 10, 350
        sort(costs.begin(),costs.end(),[](vector<int>& a, vector<int>& b){
            return a[0]-b[0] < a[1]-b[1];
        });
        // another approach is to use nth_element to achieve O(n log n) runtime
        // becuase we don't need to care much about the exact order, 
        // just find the middle as a pivot and split into two groups
        // --------------------------------APPROACH 2-------------------------------------------------
        // nth_element(begin(cs), begin(cs) + cs.size() / 2, end(cs), [](vector<int> &a, vector<int> &b) {
        //     return (a[0] - a[1] < b[0] - b[1]);
        // });
        // --------------------------------APPROACH 2-------------------------------------------------
        int ans=0, n=(int)costs.size();
        // it is guaranteed that costs.length is even
        // hence, the first half goes to city A, the second half goes to city B
        for(int i=0;i<n/2;i++) ans+=costs[i][0]+costs[i+n/2][1];
        return ans;
    }
};



/*
LeetCode - K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)


Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000
*/

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        // we don't need to care about the exact order 
        // nth_element approach should be enough
        nth_element(points.begin(),points.begin()+K,points.end(),[](vector<int>& a, vector<int>& b){
            // sort by Euclidean distance
            // dist(q,p) = sqrt( (q1-p1)*(q1-p1) + (q2-p2)*(q2-p2) )
            // since we are comparing the points with the origin (0,0)
            // dist(q,p) = sqrt( (q1)*(q1) + (q2)*(q2) )
            // and we don't need to perform sqrt as sqrt(a) must be smaller than sqrt(b) if a < b
            return a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
        });
        // resize points to show K clostest points
        points.resize(K);
        return points;
    }
};

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