Merge overlapping intervals in Python - Leetcode 56. Merge Intervals

Problem:
Given a set of intervals in arbitrary order, merge overlapping intervals to produce a list of intervals which are mutually exclusive.

Eg:
 [ [1,4], [1,5] ] --> [ [1,5] ]
[[6,8], [1,9], [2,4], [4,7]] -> [ [1, 9] ]

Approach:

This approach to solving the problem borrows the idea of how balanced parentheses are checked. We first flatten the given list of intervals into individual bounds and associate each of them with an integer which signifies whether that bound is lower or an upper bound. We then sort this list according to the starting/ending integer and then the bound i.e for the same starting/ending integer, lower bound should come before the upper bound. We use a stack and keep pushing items onto it as long as the integer represents a lower bound and pop items if it is an upper bound. If at any point of time, the stack gets empty, then we have found one merged interval.

Eg:

[ (6, 8), (1, 9), (2, 4), (4, 7) ]

Step 1: Flatten the list

[ (6, 8), (1, 9), (2, 4), (4, 7) ] -> [(6, 0), (8, 1), (1, 0), (9, 1), (2, 0), (4, 1), (4, 0), (7, 1)]

0/1 of a tuple in the resulting list tells whether it is a lower/upper bound respectively.

Step 2: Sort the flattened list

[(1, 0), (2, 0), (4, 0), (4, 1), (6, 0), (7, 1), (8, 1), (9, 1)]

Step 3: Go through the list item by item and merge as explained above.

Code:


33 comments:

  1. Windows XP was Microsoft's last stable OPERATING-SYSTEM that performed well, Alcodasoftware this OS was built using core operating procedures from the well known Home windows 98 software.

    ReplyDelete
  2. here are two variants of the demo: demo 1 and demo 2. While the variations are extremely similar, they do exhibit different characteristics. As we step through the code, those differences will be noted Bootstrap photo gallery

    ReplyDelete
  3. Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!. Igg games

    ReplyDelete
  4. Your contents are too straightforward to browse and easy to understand. interview

    ReplyDelete
  5. This is really a nice and informative, containing all information and also has a great impact on the new technology. Check it out here:
    software development company in delhi

    ReplyDelete
  6. I needed to send you one very little remark just to thank you so much once again about the superb information you have contributed above. It is remarkably generous with people like you to present freely exactly what a few people could possibly have made available as an ebook in making some bucks for their own end, notably considering that you might have tried it in case you desired. The pointers as well worked to provide a easy way to know that most people have the same zeal just as my personal own to see whole lot more with regards to this problem. I’m certain there are a lot more fun moments in the future for many who looked at your blog. how to create a programming blog

    ReplyDelete
  7. Installment plan handling: yoga studios typically offer an assortment of valuing bundles. Make it simple to offer bundles (without the hand-held mini-computer) by considering software that organizes and acknowledges installment for yoga bundles. product onboarding

    ReplyDelete
  8. i would love to see a massive price drop on internet phones coz i like to buy lots of em` python installation

    ReplyDelete
  9. The knowledge of technology you have been sharing thorough this post is very much helpful to develop new idea. here by i also want to share this.
    Devops training in tambaram
    Devops training in velachery
    Devops training in annanagar

    DevOps online Training




    ReplyDelete
  10. For a long time me & my friend were searching for informative blogs, but now I am on the right place guys, you have made a room in my heart! it support company london

    ReplyDelete
  11. Thank you for allowing me to read it, welcome to the next in a recent article. And thanks for sharing the nice article, keep posting or updating news article.
    python training institute in chennai
    python training in velachery

    ReplyDelete
  12. Thank you so much for a well written, easy to understand article on this. It can get really confusing when trying to explain it – but you did a great job. Thank you!
    Blueprism training in Chennai

    Blueprism training in Bangalore

    Blueprism training in Pune

    ReplyDelete
  13. A fascinating dialog is value remark. I feel that it is best to compose more on this matter, it may not be an unthinkable theme however generally people are insufficient to chat on such subjects. To the following. Salud. https://www.onsist.com

    ReplyDelete
  14. All the things in the blog are conveyed so elegantly.
    software outsourcing company

    ReplyDelete
  15. Thank you for benefiting from time to focus on this kind of, I feel firmly about it and also really like comprehending far more with this particular subject matter. In case doable, when you get know-how, is it possible to thoughts modernizing your site together with far more details? It’s extremely useful to me.
    java training in omr | oracle training in chennai

    java training in annanagar | java training in chennai

    ReplyDelete
  16. I’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.



    AWS Training in NewYork City | Amazon Web Services Training in Newyork City


    AWS Training in London | Amazon Web Services Training in London, UK

    Amazon Web Services Online Training in USA | AWS Online Course in USA

    ReplyDelete
  17. This comment has been removed by the author.

    ReplyDelete
  18. The quicker the info can be requested and conveyed, the less the requirement for an extensive stock. Angular testing services software testing

    ReplyDelete
  19. When you are building up a basic site, the subject of which programming dialect and system to pick can come up for things, for example, contact accommodation frames, photograph displays, jQuery Slider or whatever other powerful substance segments that is created by the web-server. how to learn coding fast

    ReplyDelete
  20. experience. But reading between the lines, this simply means that they have five years experience anywhere in the field of Information Technology.dbdesigner.net

    ReplyDelete
  21. Without a doubt, an accurately picked ERP arrangement takes care of the issues of detached and divided software forms by making a reasonable, effective, and solid software condition with gigantic advantages. branded exercises prescription software

    ReplyDelete
  22. Your good knowledge and kindness in playing with all the pieces were very useful. I don’t know what I would have done if I had not encountered such a step like this.
    devops online training

    aws online training

    data science with python online training

    data science online training

    rpa online training

    ReplyDelete
  23. The Best Cryptocurrency Exchange Game The Argument About Best Cryptocurrency Exchange Bitcoinbing, being an exchange can barely leave a stone unturned to produce the security foolproof. It's possible for you to learn currency crypto exchange
    and receive a robust method together in about two weeks and after that you can get the job done just 30 minutes daily, on your computer and make great FX Profits. If you wish to learn currency exchange then you have to acquire the most suitable forex education and ignore a good deal of so called accepted wisdoms. The foreign currency exchange risky and you will need to find expert advice if you are interested in being making money with Forex trading.

    ReplyDelete
  24. I appreciated your work very thanks typing tutor

    ReplyDelete
  25. As one bound together arrangement, ERP software builds up professionalized business schedules just as responsibility and availability all through the organization. https://www.techpally.com/mynetdiary-calories-counter/

    ReplyDelete
  26. I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing.
    Rex Almaraz

    ReplyDelete