#include "misc.h"
#include "data.h"
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
class Order {
private:
int _pid;
int _quantity;
int _expected_days;
Region _region;
double _date;
public:
Order (int pid_, int quantity_, int expected_days_, Region region_, double date_) :
_pid (pid_),
_quantity (quantity_),
_expected_days (expected_days_),
_region (region_),
_date (date_) {};
Order (const Order &other_) {
_pid = other_._pid;
_quantity = other_._quantity;
_expected_days = other_._expected_days;
_region = other_._region;
_date = other_._date;
}
const int getPid () const { return _pid; }
const int getQuantity () const { return _quantity; }
const Region getDestination () const { return _region; }
};
class ProductInventory {
private:
int _pid;
int _quantity;
Region _region;
public:
ProductInventory (int pid_, int quantity_, Region region_) :
_pid (pid_),
_quantity (quantity_),
_region (region_) {};
ProductInventory (const ProductInventory &other_) {
_pid = other_._pid;
_quantity = other_._quantity;
_region = other_._region;
}
const int getPid () const { return _pid; }
const int getQuantity () const { return _quantity; }
void reduceQuantity (int val) { _quantity -= val; }
const Region getRegion () const { return _region; }
};
class ShippingCost {
private:
Region _ship_from;
Region _ship_to;
Method _method;
int _cost_per_item;
int _days;
public:
ShippingCost (Region ship_from_, Region ship_to_, Method method_, int cost_per_item_, int days_) :
_ship_from (ship_from_),
_ship_to (ship_to_),
_method (method_),
_cost_per_item (cost_per_item_),
_days (days_) {};
ShippingCost (const ShippingCost &_other) {
_ship_from = _other._ship_from;
_ship_to = _other._ship_to;
_method = _other._method;
_cost_per_item = _other._cost_per_item;
_days = _other._days;
}
const Region getShipFrom () const { return _ship_from; }
const Region getShipTo () const { return _ship_to; }
const int getDays () const { return _days; }
const int getCost () const { return _cost_per_item; }
};
//data----------------------------------------------------------------
const static vector<Order> orders {
Order (1, 6, 4, center, 0.3),
Order (1, 3, 2, west, 0.0),
Order (1, 4, 0, east, 0.2),
Order (3, 100, 0, center, 0.1),
Order (2, 6, 4, center, 0.3)
};
static vector<ProductInventory> productInventoryList {
ProductInventory (1, 7, north),
ProductInventory (3, 70, north),
ProductInventory (3, 20, north),
ProductInventory (3, 40, east),
ProductInventory (3, 30, north),
};
const static vector<ShippingCost> shippingCostList {
ShippingCost (north, west, express, 3, 10),
ShippingCost (north, west, ground, 1, 15),
ShippingCost (north, east, ground, 2, 20),
ShippingCost (north, center, express, 2, 5)
};
//---------------------------------------------------------------
class ProductShippingCost{
public:
ProductInventory productInventory;
vector<ShippingCost> shippingCostList;
ProductShippingCost(ProductInventory productInventory, vector<ShippingCost> shippingCostList): productInventory(productInventory), shippingCostList(shippingCostList){}
};
//milestone 1
vector<ProductShippingCost> Solution1(int pid, Region toRegin) {
vector<ProductShippingCost> result;
for(ProductInventory& currentInventory : productInventoryList) {
//if currentInventory contains the product we want
if (pid == currentInventory.getPid()) {
ProductShippingCost temp(currentInventory,{});
for (ShippingCost currentShippingCost : shippingCostList) {
if (currentShippingCost.getShipFrom() == currentInventory.getRegion() &&
currentShippingCost.getShipTo() == toRegin) {
temp.shippingCostList.push_back(currentShippingCost);
}
}//for shippingCostList
//if there exist a way that the product can be shipped to the destination
if(!temp.shippingCostList.empty()) result.push_back(temp);
}
}//for productInventoryList
return result;
}
struct OrderQuantityComparator {
bool operator () (const Order &order1, const Order &order2) {
return order1.getQuantity() < order2.getQuantity();
}
} orderQuantityComparator;
struct ShippingCostTimeComparator {
bool operator () (ShippingCost shippingCost1, ShippingCost shippingCost2) {
return shippingCost1.getDays() < shippingCost2.getDays();
}
}shippingCostTimeComparator;
//void Solution2() {
// vector<Order> orderList = orders;
// sort(orderList.begin(),orderList.end(),orderQuantityComparator);
//
// for(Order& order : orderList) {
//
// vector<ProductShippingCost> orderShippingCostList = Solution1(order.getPid(), order.getDestination());
// //orderShippingCostList -> { productInventory, vector<shippingCost> }
//
// unordered_map<ShippingCost,ProductInventory> productInventoryToMinTime;
//
//
//
// int inventoryQuantitySum = 0;
//
// //for one specific inventory
// for(ProductShippingCost& orderShippingCost : orderShippingCostList) {
// inventoryQuantitySum += orderShippingCost.productInventory.getQuantity();
//
// int minShppingTime = 99999;
// ShippingCost minTimeShipping = orderShippingCost.shippingCostList[0];
//
// //get current inventory's shippingCost with least shipping time
// for (ShippingCost& shippingCost : orderShippingCost.shippingCostList) {
// if (shippingCost.getDays() < minShppingTime) {
// minShppingTime = shippingCost.getDays();
// minTimeShipping = shippingCost;
// }
// }
// //productInventoryToMinTime[minTimeShipping] = orderShippingCost.productInventory;
//
// //Now we have productInventoryToMinTime<ProductInventory,ShippingCost> ordered by shippingTime
// }
//
//// if(inventoryQuantitySum < order.getQuantity()) continue;
////
//// int unfinishedQuantity = order.getQuantity();
//// while(unfinishedQuantity > 0)
//// {
//// ProductInventory currentInventory = productInventoryToMinTime.begin()->first;
//// currentInventory.reduceQuantity(min(currentInventory.getQuantity(), unfinishedQuantity));
//// unfinishedQuantity -= min(currentInventory.getQuantity(), unfinishedQuantity);
//// cout << "from Inventory " << currentInventory.getRegion() << " ship " << min(currentInventory.getQuantity(), unfinishedQuantity) << endl;
//// if(currentInventory.getQuantity() == 0) productInventoryToMinTime.erase(currentInventory);
//// }
//
// }
//
//
//}
//
typedef pair<ProductInventory *, int> InventoryMinTimePair;
struct InventoryMinTimePairComparator {
bool operator()(const InventoryMinTimePair & InventoryMinTimePair1,const InventoryMinTimePair & InventoryMinTimePair2) {
return InventoryMinTimePair1.second < InventoryMinTimePair2.second;
}
};
void Solution22(vector<Order> orderList) {
sort(orderList.begin(),orderList.end(),orderQuantityComparator);
for(Order& order : orderList) {
cout << "Order " << order.getPid() << endl;
//Order shipping plan selection part:
vector<ProductShippingCost> productShippingCostList = Solution1(order.getPid(), order.getDestination());
priority_queue<InventoryMinTimePair,vector<InventoryMinTimePair>, InventoryMinTimePairComparator> productInventoryPQ;
//iterator in this loop has form { productInventory, vector<shippingCost> }
for(ProductShippingCost & productShippingCost : productShippingCostList) {
//there is no way the product can be shipped
if(productShippingCost.shippingCostList.empty()) continue;
int inventoryQuantitySum = 0;
//GOAL: select the least time shippingCost from vector<shippingCost>
// and save it to a pq of pair <procuetInventory, shippingCostMinTime>
int minTime = productShippingCost.shippingCostList[0].getDays();
InventoryMinTimePair productInventoryWithMinTimeShipping;
//O(N), N = size of shippingCostList, Linear search
for(ShippingCost &shippingCost : productShippingCost.shippingCostList) {
minTime = min(minTime,shippingCost.getDays());
} //for shippingCost
productInventoryWithMinTimeShipping.first = &productShippingCost.productInventory;
productInventoryWithMinTimeShipping.second = minTime;
//O(logN), N = #inventories contains current product, PQ push in C++
//Now we get a pq contains all the inventorys sorted by the shipping time
productInventoryPQ.push(productInventoryWithMinTimeShipping);
inventoryQuantitySum += productShippingCost.productInventory.getQuantity();
//Order can NOT be fulfilled
if(inventoryQuantitySum < order.getQuantity()) continue;
//Inventory shipping part:
int unShippedCount = order.getQuantity();
while(unShippedCount > 0 ) {
//inventory can at most ship all its products
int shipQuaitity = min(productInventoryPQ.top().first->getQuantity(),unShippedCount);
productInventoryPQ.top().first->reduceQuantity(shipQuaitity);//O(1)
cout << "Ship " << shipQuaitity << " from inventory " << productInventoryPQ.top().first->getRegion() << endl;
productInventoryPQ.pop();//O(logN), N = size of PQ
unShippedCount -= shipQuaitity;
}
} //for productShippingCost
}
}
struct InventoryMinCostPairComparator {
bool operator()(const InventoryMinTimePair & InventoryMinCostPair1,const InventoryMinTimePair & InventoryMinCostPair2) {
return InventoryMinCostPair1.second < InventoryMinCostPair2.second;
}
};
void Solution3(vector<Order> orderList) {
sort(orderList.begin(),orderList.end(),orderQuantityComparator);
for(Order& order : orderList) {
cout << "Order " << order.getPid() << endl;
//Order shipping plan selection part:
vector<ProductShippingCost> productShippingCostList = Solution1(order.getPid(), order.getDestination());
priority_queue<InventoryMinTimePair,vector<InventoryMinTimePair>, InventoryMinTimePairComparator> productInventoryPQ;
//iterator in this loop has form { productInventory, vector<shippingCost> }
for(ProductShippingCost & productShippingCost : productShippingCostList) {
//there is no way the product can be shipped
if(productShippingCost.shippingCostList.empty()) continue;
int inventoryQuantitySum = 0;
//GOAL: select the least time shippingCost from vector<shippingCost>
// and save it to a pq of pair <procuetInventory, shippingCostMinTime>
int minCost = productShippingCost.shippingCostList[0].getCost();
InventoryMinTimePair productInventoryWithMinTimeShipping;
//O(N), N = size of shippingCostList, Linear search
for(ShippingCost &shippingCost : productShippingCost.shippingCostList) {
minCost = min(minCost,shippingCost.getDays());
} //for shippingCost
productInventoryWithMinTimeShipping.first = &productShippingCost.productInventory;
productInventoryWithMinTimeShipping.second = minCost;
//O(logN), N = #inventories contains current product, PQ push in C++
//Now we get a pq contains all the inventorys sorted by the shipping time
productInventoryPQ.push(productInventoryWithMinTimeShipping);
inventoryQuantitySum += productShippingCost.productInventory.getQuantity();
//Order can NOT be fulfilled
if(inventoryQuantitySum < order.getQuantity()) continue;
//Inventory shipping part:
int unShippedCount = order.getQuantity();
while(unShippedCount > 0 ) {
//inventory can at most ship all its products
int shipQuaitity = min(productInventoryPQ.top().first->getQuantity(),unShippedCount);
productInventoryPQ.top().first->reduceQuantity(shipQuaitity);//O(1)
cout << "Ship " << shipQuaitity << " from inventory " << productInventoryPQ.top().first->getRegion() << endl;
productInventoryPQ.pop();//O(logN), N = size of PQ
unShippedCount -= shipQuaitity;
}
} //for productShippingCost
}
}
struct testComp {
bool operator()(const string &a ,const string &b) const {
return a < b;
}
}comp;
int main(int argc, const char * argv[]) {
vector<ProductShippingCost> result = Solution1(3, west);
//cout << result.size() << endl;
//Solution2(orderList);
// map<string,int,testComp> test;
// test["hjq"] = 3;
// test["12"] = 4;
// test["kkk"] = 2;
// test["asdf"] = 1;
// test["34234"] = 5;
// test["asdfg"] = 9;
// for(auto it : test) {
// cout << it.second << endl;
// }
Solution22(orders);
return 0;
}
myCode
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
