We derive a necessary and sufficient condition for the possibility of achieving the Heisenberg scaling in general adaptive multi-parameter estimation schemes in presence of Markovian noise. In situations where the Heisenberg scaling is achievable, we provide a semidefinite program to identify the optimal quantum error correcting (QEC) protocol that yields the best estimation precision. We overcome the technical challenges associated with potential incompatibility of the measurement optimally extracting information on different parameters by utilizing the Holevo Cramer-Rao (HCR) bound for pure states. We provide examples of significant advantages offered by our joint-QEC protocols, that sense all the parameters utilizing a single error-corrected subspace, over separate-QEC protocols where each parameter is effectively sensed in a separate subspace.