Hybrid clouds have gained popularity in recent times in a variety of organizations due to their ability to provide additional capacity in a public cloud, to augment private cloud capacity, when it is needed. However, scheduling distributed applications' jobs (e.g, workflow tasks) on hybrid cloud resources introduces new challenges. One key problem is the danger of exposing private data and jobs in a third-party public cloud infrastructure, for example in healthcare applications. In this article, we tackle the problem of designing workflow scheduling algorithms to meet customers' deadlines, while not compromising data and task privacy requirements. Our work is different from most studies on workflow scheduling where the main goal is to achieve a balance between desirable, yet incompatible constraints, such as meeting the deadline and/or minimizing the execution time. Although many others have addressed the trade-off between cost and time, or privacy and cost, their work still suffers from an insufficient consideration of the trade-off between privacy and time. To address such shortcomings in the literature, we present a new SaaS scheduling broker composed of MPHC-P1, MPHCP2, and MPHC-P3 policies to preserve privacy while scheduling the workflows' tasks under customers' deadlines. We evaluated our approach using real workflows running on a VMware based hybrid cloud. Results demonstrate that under our scheduling policies, MPHC-P2 and MPHC-P3 are promising in time-critical scenarios by reducing the total cost by 10-20 percent compared to alternatives. Overall, results show that our approach is efficient in reducing the cost of executing workflows while satisfying both their privacy and deadline constraints.