This letter proposes an efficient Two-stage Resource scheduling algorithm for cloud based Live Media Streaming system (TRLMS). It transforms the cloud-based resource scheduling problem to a min-cost flow problem in a graph, and solves it by an improved Successive Short Path (SSP) algorithm. Simulation results show that TRLMS can enhance user demand satisfaction by 17.1% than mean-based method, and its time complexity is much lower than original SSP algorithm.