0

I'm trying to solve Kattis problem Compass Card Sales. For this I have a List of Card objects which have uniqueness property. I have to start removing cards with the least uniqueness and recalculate uniqueness value after each removal.

My solution works but it can't pass 8th test case due to time limit. I tried keeping cards as a SortedSet but it worked worse than List. Then I tried with HashSet but it didn't make any difference.

while (CardList.Count > 1)
            {
                CalculateUniqueness();

                Card leastUnique = CardList.Min();
                //Card leastUnique = CardList.OrderBy(p => p.TotalUniqueness).ThenByDescending(p => p.Id).First();

                Console.WriteLine(leastUnique.Id);

                CardList.Remove(leastUnique);
            }

Edit: CompareTo method of Card class:

public int CompareTo(object obj)
        {
            Card otherCard = (Card)obj;
            int uniquenessComparison = TotalUniqueness.CompareTo(otherCard.TotalUniqueness);
            if (uniquenessComparison != 0)
            {
                return uniquenessComparison;
            }
            else
            {
                return otherCard.Id.CompareTo(Id);
            }
        }
ggorlen
  • 44,755
  • 7
  • 76
  • 106
user2560178
  • 31
  • 5
  • If you need to keep removing a minimum element I suggest you use a priority queue. Unfortunately there isn't one in the BCL. – Lee Nov 04 '19 at 13:58
  • This may help you: [HashSet vs. List performance](https://stackoverflow.com/questions/150750/hashset-vs-list-performance) and [HashSet vs List vs Dictionary](https://theburningmonk.com/2011/03/hashset-vs-list-vs-dictionary/). HashSet, if applicable, is best if large amount of items and the performance remains stable. –  Nov 04 '19 at 14:07
  • Possible duplicate of [HashSet vs. List performance](https://stackoverflow.com/questions/150750/hashset-vs-list-performance) –  Nov 04 '19 at 14:08
  • @OlivierRogier Thanks, with small datasets there is no performance problem. With large datasets it exceeds the time limit. – user2560178 Nov 05 '19 at 05:12

0 Answers0