So sorry if I'm not using this feature properly, I was struggling with a problem and thought this would be a good place to ask for help. So here's the problem:
There are N light bulbs. Initially, all of them are turned off. You are given M switches with which you can switch the light bulbs on and off. The i-th switch will switch all the light bulbs in the subsequence starting at A[i] and ending at B[i] (All the turned off light bulbs are switched on and all the switched on ones are turned off).
You are also given a number X. Your job is to end with the light bulbs from 1 to X on, and all the ones from X+1 to N off, using the minimum number of switches possible.
Output the minimum number of switches to achieve the goal. If it is not possible to achieve the goal, output -1.
The input file are the numbers N M X followed by M (the number of switches) lines in which the i th line is A[i] and B[i] (the parameters for the switches)
N<=100 000 M<=200 000 example: IN OUT 5 3 4 3 1 3 3 4 3 3
Let's define dist[i] as the minimum number of switch presses to have all the lamps from 1 to i ON and the others OFF.
If we have a switch (a[i] , b[i]) =>
dist[a[i] — 1] = min(dist[a[i]-1] , dist[b[i]] + 1) because we can turn the lamps from a[i] to b[i] off
dist[[b[i] ] = min(dist[b[i]] , dist[a[i]-1] + 1) , we can extend our interval by turning the lamps on
Since it would be too much trouble to compute dist[i] we can solve an equivalent problem : given a graph with edges (a[i]-1)->(b[i]) compute the distance from node 0 to node x. Transforming a recurrence relationship into a graph is actually quite a common problem.
If someone is interested in the problem : https://www.infoarena.ro/problema/pcb (this site is in romanian , I couldn't find the problem in english)
EDIT: I see that I got a lot of downvotes , I am not telling you not to downvote me , but if you really want to downvote please tell me what did I do wrong so as to improve my answers and also be able to help more people.