Operating rooms are the financial engine of modern hospitals, yet their scheduling remains paralysed by a fundamental paradox: how to plan precisely in an environment defined by chaos and uncertainty. Traditional methods, relying on static averages, systematically fail to capture the long tail of surgical variability, leading to costly gaps between planned capacity and operational reality. To address this challenge, we propose a learning framework that models heterogeneity in surgical workflows. Surgical cases are first grouped using Ordering Points To Identify the Clustering Structure (OPTICS) density-based clustering, revealing distinct behavioral groups within a dataset of more than 143,524 cases from the CHC Healthcare Group in Belgium. Depending on these groups, group-specific Gradient Boosting models are trained, reducing the Mean Absolute Error (MAE) to 13.85 min and improving planning adherence by approximately 19% compared to standard baselines. To explicitly account for residual uncertainty, we apply Quantile Regression to estimate prediction intervals, capturing the risk of unobserved delays such as transition time between surgeries. Rather than relying on single-point predictions, the proposed approach provides explicit uncertainty quantification for the following scheduling decisions. In general, this framework separates capacity estimation from schedule timing and enables more robust, uncertainty-aware operating room planning.