मान लीजिए N कारें हैं जो एक लेन वाली सड़क के साथ एक ही गंतव्य की ओर जा रही हैं। गंतव्य 'target' मील दूर है। अब प्रत्येक कार i की एक स्थिर गति मान speed[i] (मील प्रति घंटे में) है, और प्रारंभिक स्थिति सड़क के साथ लक्ष्य की ओर position[i] मील है।
एक कार अपने आगे वाली कार को कभी पार नहीं कर सकती, लेकिन यह उसके पास पहुंच सकती है, और उसी गति से बम्पर-टू-बम्पर चल सकती है। यहां इन दो कारों के बीच की दूरी को नजरअंदाज किया जाता है - उन्हें समान स्थिति माना जाता है। एक कार फ्लीट कारों का कुछ गैर-खाली समूह है जो समान स्थिति और समान गति से चल रहा है। यदि एक कार गंतव्य बिंदु पर एक कार फ्लीट को पकड़ लेती है, तो इसे अभी भी एक कार फ्लीट माना जाएगा। तो हमें यह पता लगाना है कि कितने कार फ्लीट गंतव्य पर पहुंचेंगे।
तो यदि लक्ष्य 12 है, यदि स्थिति [10,8,0,5,3] है और गति [2,4,1,1,3] है तो आउटपुट 3 होगा। ऐसा इसलिए है क्योंकि 10 और 8 से शुरू होने वाली कारें एक फ्लीट बन जाती हैं, जो 12 पर एक-दूसरे से मिलती हैं। अब 0 से शुरू होने वाली कार किसी अन्य कार को नहीं पकड़ती, इसलिए यह अपने आप में एक फ्लीट है। फिर 5 और 3 से शुरू होने वाली कारें एक फ्लीट बन जाती हैं, जो 6 पर एक-दूसरे से मिलती हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक सरणी v बनाएं, n := स्थिति सरणी p का आकार
- i को 0 से n - 1 की रेंज में
- (p[i], s[i]) को v में डालें
- ret := n
- v सरणी को सॉर्ट करें
- एक स्टैक st परिभाषित करें
- i को 0 से n - 1 की रेंज में
- temp := (t - v[i] का पहला तत्व) / v[i] का दूसरा तत्व
- जब तक st खाली नहीं है और स्टैक टॉप <= temp
- ret को 1 से घटाएं
- st से टॉप तत्व हटाएं
- temp को st में डालें
- ret लौटाएं।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int carFleet(int t, vector<int>& p, vector<int>& s) {
vector < pair <double, double> > v;
int n = p.size();
for(int i = 0; i < n; i++){
v.push_back({p[i], s[i]});
}
int ret = n;
sort(v.begin(), v.end());
stack <double> st;
for(int i = 0; i < n; i++){
double temp = (t - v[i].first) / v[i].second;
while(!st.empty() && st.top() <= temp){
ret--;
st.pop();
}
st.push(temp);
}
return ret;
}
};
main(){
vector<int> v1 = {10, 8, 0, 5, 3};
vector<int> v2 = {2,4,1,1,3};
Solution ob;
cout << (ob.carFleet(12, v1, v2));
}
इनपुट
12 [10,8,0,5,3] [2,4,1,1,3]
आउटपुट
3
