1 / 9
Nov 2020

Here’s one. Expected answer is 3, your answer is 2.

1
5
2 3
5 6
2 4
3 5
4 7

Thank You for your reply.

I have solved that issue and used multimap

As we know, map has a complexity of insertion and deletion is O(1) and binary search has a complexity of O(logn).

My code has a complexity of O(nlog(n)). Then why it is giving TLE ?

My solution: https://pastebin.ubuntu.com/p/TnV9f9HMqt/4

There are two problems that I can see. Either alone means that a simple test case with 5 lines exceeds the 15 seconds runtime allowed on ideone.

What does this do, and why might it cause a problem?

what may happen to the iterator here?

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

I have used it for faster input output though i’ve used scanf prinf. Link1

tFinish_idx.erase(it)

It is for erasing finish time from the multimap. Editing map’s index is not valid. So i erased it first then inserted it with new finishing time .

What shouldn’t you do after using ios::sync_with_stdio(0)?

And what may happen to the iterator after using tFinish_idx.erase(it)?

ios::sync_with_stdio(0)

this has no use here. So we can remove this.

tFinish_idx.erase(it)

this will delete the previous finishing time of a lecture in determined room.

You are using both cin and scanf - so what effect does ios::sync_with_stdio(0) have on that? The answer is that n would get some very strange values, far larger than you might expect.

I know why you’re using tFinish_idx.erase(it), but you’re not answering the question - what may happen to the ITERATOR after using using it? See www.cplusplus.com/reference/map/multimap/erase/. Iterators, pointers and references referring to elements removed by the function are invalidated. The iterator is invalidated, but you still continue to use it.

Thank you for your reply. This time, I’ve found out my mistake, Thanks a lot. I’ve learned a new thing from here.

Will it be the same O(n^2), if i use priority queue and erase function here?