Can someone explain me the time complexity of my solution for the ZCO 2015 problem “Covering”. I am still not sure whether it is O(n*log(n)) or O(n^2) as both are supposed to give AC.
For every interval you are adding, you are iterating the entire set to check if it might be intersecting with any other interval. It might look like O({N}^{2}LogN), but one needs to compute maximum elements traversed in the set every iteration to conclude that.
I feel your inner loop wont iterate more than a few times. You’re starting from end point of an interval which is the smallest possible number, say k greater than l where [l,r] is the current interval under investigation. We know that k \ge l. If k \le r then we found an integer and exit the loop. If k > r then the loop condition doesnt hold and we exit.
Hence, O(NlogN) in my opinion, the logN factor coming from usage of sets.