Data privacy preservation has drawn much attention with emerging machine learning applications. Federated Learning is thus developed to offer decentralized learning on user devices. However, it is difficult to jointly address multiple issues such as device selection, upload scheduling, and payment minimization. To jointly optimize the issues above, we first formulate a new optimization problem, named TRAIN, to minimize the training cost (including incentive payment and upload time) while ensuring the data requirement. We then prove the NP-hardness and propose a 3-approximation algorithm, named DETECT to obtain a near-optimal solution. Simulation results manifest that DETECT reduces the training cost by 50% compared with other traditional methods and achieves high accuracy and short convergence time.