High-quality video, both uncompressed and compressed with relatively low compression ratio, is used in interactive environments, where minimum end-to-end latency is required. The media streams planning solves multi-point data routing for such applications even when bit rate of streams is comparable to capacity of network links. Recent advances in acceleration of high-throughput low-latency video processing enable on-the-fly video transcoding even for 4K and 8K video streams, thus allowing individual adaptation of data stream for each recipient without affecting the others. Stimulated by these advances, we present a novel media streams planning with transcoding on network nodes, and a mixed integer programming approach to solve the problem optimally. Our approach also enhances traditional end-to-end network model of the whole system with known topology of certain network regions. Our solution was implemented in the Co Universe, which is middleware for orchestration of collaborative environments. Measurements show that performance of the new solver is sufficient for interactive solving of most practical use-cases, thus enabling self-organization of high-performance collaborative environments.