In this letter, we study a completion-time minimization problem by jointly optimizing time slots (TSs) and power allocation for time-critical non-orthogonal multiple access (NOMA) systems. The original problem is non-linear/non-convex with discrete variables, leading to high computational complexity in conventional iterative methods. Towards an efficient solution, we train deep neural networks to perform fast and high-accuracy predictions to tackle the difficult combinatorial parts, i.e., determining the minimum consumed TSs and user-TS allocation. Based on the learning-based predictions, we develop a low-complexity post-process procedure to provide feasible power allocation. The numerical results demonstrate promising improvements of the proposed scheme compared to other baseline schemes in terms of computational efficiency, approximating optimum, and feasibility guarantee.