LeetCode #1094 CarPooling. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
Runtime: 8 ms, faster than 92.62% of C++ online submissions for Car Pooling.
Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Car Pooling.
LeetCode #1094
Q.
You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)
Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle's initial location.
Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.
capacity 만큼 승객을 태울 수 있는 차를 운전하고 있다. 차는 동쪽 방향으로만 움직일 수 있다.
trips 리스트가 주어지는데, 그 안의 trip[i] = [승객 수, 태우는 위치, 내리는 위치] 정보를 포함하고 있다. 승객 수만큼 태워야 하고, 태웠다가 내려줘야 한다. 위치는 시작점으로부터 동쪽으로의 키로수를 나타낸다.
주어진 trips 의 승객들을 모두 태우고 내려줄 수 있는지 여부를 반환해라.
Example 1:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true
Constraints:
- trips.length <= 1000
- trips[i].length == 3
- 1 <= trips[i][0] <= 100
- 0 <= trips[i][1] < trips[i][2] <= 1000
- 1 <= capacity <= 100000
Process
// Process
//1. Input trips vector and capacity
//2. Get the most far end location
//3. Make start/end location passenger array
//4. Iterate location array
// 4.1. Check if it has number of passengers to pick or drop
// 4.1.1. If to pick -> reduce capacity
// 4.1.1.1. Check capacity is under 0 or not
// 4.1.1.1.1. If so -> result is false
// 4.1.2. If to drop -> recover capacity
//5. Return result
// 처리과정
//1. trips 리스트와 capacity 를 입력받는다.
//2. 가장 먼거리 승객들의 위치를 구해둔다.
//3. 태우는곳/내리는곳 인원 배열을 만들어둔다.
//4. 위치인원배열 전체 반복한다.
// 4.1. 태우거나 내릴 사람이 있는지 확인해서
// 4.1.1. 태우게되면 -> capacity 를 줄인다.
// 4.1.1.1. capacity 가 0보다 작아지면 결과는 false
// 4.1.2. 내리게 되면 capacity 를 회복시켜둔다.
//5. 결과 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
bool result = true;
int mostFarDestination = 0;
// 2.
for (int i = 0; i < trips.size(); ++i) {
if (mostFarDestination < trips[i][2])
mostFarDestination = trips[i][2];
}
// 3.
int* locationArray = new int[mostFarDestination];
for (int i = 0; i < mostFarDestination; ++i) {
locationArray[i] = 0;
}
for (int i = 0; i < trips.size(); ++i) {
locationArray[trips[i][1] - 1] += trips[i][0];
locationArray[trips[i][2] - 1] -= trips[i][0];
}
// 4.
for (int i = 0; result && i < mostFarDestination; ++i) {
if (locationArray[i] > 0) {
capacity -= locationArray[i];
if (capacity < 0)
result = false;
}
else if (locationArray[i] < 0) {
capacity -= locationArray[i];
}
}
return result;
}
};
Something else you might like...?
2019/08/14 - [Life/Item review] - Mi Band 4 review, 미밴드4 후기, 장점, 단점, 리뷰, 한글, global review, 미밴드4 글로벌 후기, 리뷰, 구매, 사용방법, setting, 세팅, ProsNCons
2019/08/27 - [Programming] - 개발자 선배들에게서 배운 것들. Things I Learnt from a Senior Software Engineer. 코딩 잘하는 방법, how to code well, 소프트웨어,프로그래머,programmer
2019/09/17 - [Algorithm/Leet Code] - LeetCode #841 KeysAndRooms. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/08/28 - [Algorithm/Leet Code] - LeetCode #821 ShortestDistanceToACharacter. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접..
2019/08/25 - [Algorithm/Leet Code] - LeetCode #191 NumberOf1Bits. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/08/19 - [Algorithm/Leet Code] - LeetCode #942 DI StringMatch. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/07/21 - [Algorithm/Leet Code] - LeetCode #590 N-aryTreePostorderTraversal. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,..
2019/07/20 - [Algorithm/Leet Code] - LeetCode #589 N-aryTreePreorderTraversal. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,..
2019/07/17 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리..
2019/07/13 - [Algorithm/Leet Code] - LeetCode #994 RottingOranges. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/06/25 - [Algorithm/Leet Code] - LeetCode #766 ToeplitzMatrix. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
2019/04/14 - [Programming/C++] - C++ Math - sqrt (square root, 제곱근, 루트). stl, math.h, 씨쁠쁠, example code, 예제코드
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/16 - [Life/Health care] - Finasteride 피나스테라이드,탈모약 usage/side effects/dosage 효능/부작용/효과/sexual effect/두타스테라이드/프로페시아/propecia/finpecia/카피약/copy drug/hair loss
2019/02/25 - [Life/Health care] - Folic Acid 엽산 vitaminB9,비타민M usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법
2019/03/03 - [Life/Health care] - Vitamin B1, Thiamine, 비타민 B1, 티아민 usage/side effects/dosage 효능/부작용/성인,소아 용법
