Both live and offline transcoding of media is managed for storage in a cache. Requests for media are made by a client on a network and media taken from the cache and transcoded for delivery to the client. Media is also transcoded and stored in memory during idle request in anticipation of future requests during idle transcoder time between client requests. A prioritizer manages at least offline transcoding requests. A high priority queue operates at a higher priority than the low priority queue. The high priority queue receives live transcoding requests from a client on the network. A low priority queue receives offline transcoding requests. A media transcoder primarily transcodes media in accordance with requests from the high priority queue for delivery to a client on the network and then secondarily transcodes media in accordance with requests from the low priority queue when the high priority queue is empty. According to alternative embodiments the media transcoder transcodes media into segments and to modify frames when necessary to insure that they are decodable without accessing other segments.