I'm a strength trainee, but when I realized I was getting way out of CV shape from Starting Strength I did the C25k program. The android app is amazing, although it is much better if you can use it outside because it tracks interval speed. I would RUN during the run portion, striving for personal records.
To the question asker, I say go for it but don't give up on your strength training. What I would do is run my C25k program around a nearby lake, and then stop at the playground (I ran at night so it was empty) for a bodyweight circuit of pushups, dips, pullups, and bodyweight squats/lunges. I didn't lose any strength without barbells (I may have gained a bit), and I gained quite a bit of flexibility.
I have done a version of the C25K program before and when it helped me for what purposes I needed it for at that time. I think it's a fine program and have seen a lot of people make some good advances on it.
As for HIIT and sprinting, I think Tabata was mentioned already. If you can sprint for 20 seconds, then you can do Tabata to help you more with that and knock out those HIIT sessions. Try once a week. You would sprint for 20 seconds, then walk 10, repeat 8 times. And you're done.
~All luck is earned in the end.~